B. Сережа ба тэмцээнүүд

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Сережа код бичдэг ба Кодсорфесийн тэмцээнүүдэд оролцох дуртай. Гэсэн ч Узлэндэд сайн интернет холболт байхгүй ба Сережа заримдаа тэмцээнүүдийг алгасадаг.

Кодсорфесийн тэмцээнүүд хоёр төрөлтэй: $Div1$ (ахисан түвшний код бичигчдэд зориулсан) ба $Div2$ (эхлэн суралцаж буй код бичигчдэд зориулсан). $Div1$ ба $Div2$ тэмцээнүүд нь зэрэг явагдаж болно ($Div1$ раунд $Div2$-гүйгээр зохиогдохгүй) бусад тохиолдолд раундууд давхцаж болохгүй. Раунд бүр давтагдашгүй тодорхойлогч болох бүхэл тоотой. Раундууд дарааллан (дундаа зайгүй) раундын эхлэх хугацаагаараа тодорхойлогчуудаар дугаарлагдана. Зэрэг явагдах раундуудын тодорхойлогчууд нэг тооны зөрүүтэй байх ба $Div1$ раундын тодорхойлогч үргэлж их байна.

Сережа бол эхлэн суралцаж буй код бичигч учраас зөвхөн $Div2$ төрлийн раундууд л оролцож чадна. Тэр $Div2$ раундад оролцож байх мөчид үүний тодорхойлогч $x$-тэй тэнцүү байв. Сережа энэ раундын өмнө яг $k$ раундад оролцсоноо маш сайн санаж байна. Мөн тэр өөрийн оролцсон бүх раундуудынхаа тодорхойлогчийг санаж байгаа ба эдгээр раундуудтай зэрэг явагдаж байсан бүх раундуудын тодорхойлогчийг санаж байна. Сережа алгассан раундуудынхаа талаар юу ч санахгүй байна.

Сережа өөрийн алгассан $Div2$ төрлийн раундуудын хамгийн бага болон хамгийн их тоо хэд юм бол? гэж гайхаж байна. Түүнд энэ хоёр тоог олоход туслана уу.

Оролт

Эхний мөрөнд хоёр бүхэл тоон утга: $x$ $(1 ≤ x ≤ 4000)$ буюу Сережагийн өнөөдөр орж буй раунд ба $k$ $(0 ≤ k < 4000)$ тэрний оролцсон раундуудын тоо байна.

Дараагийн $k$ мөрөнд Сережагийн өмнө нь оролцсон раундуудын тодорхойлолт байна. Хэрвээ Сережа зэрэг болж буй хоёр раундуудын нэгэнд оролцсон бол харгалзах мөр нь: "1 $num_{2}$ $num_{1}$" (энд $num_{2}$ нь уг $Div2$ раундын тодорхойлогч, $num_{1}$ нь $Div1$ раундын тодорхойлогч юм) хэлбэртэй байна. $num_{1} - num_{2} = 1$ байх нь тодорхой. Хэрвээ Сережа энгийн $Div2$ раундад оролцсон бол харгалзах мөр нь: "2 $num$" (энд $num$ нь $Div2$ раундын тодорхойлогч) хэлбэртэй байна. Өгөгдсөн бүх раундуудын тодорхойлогч нь $x$-с бага байх нь тодорхой.

Гаралт

Сережагийн алгассан байж болох раундуудын хамгийн бага болон хамгийн их тоо болох хоёр бүхэл тоог нэг мөрөнд хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
3 2
2 1
2 2
Гаралт
0 0
Оролт
9 3
1 2 3
2 8
1 4 5
Гаралт
2 3
Оролт
10 0
Гаралт
5 9

Тэмдэглэл

Хоёр дахь жишээн дээр бид раундуудын 1, 6, 7 тодорхойлогчуудыг ашиглаагүй. Сережагийн алгассан байж болох раундуудын хамгийн бага тоо нь 2-той тэнцүү. Энэ тохиолдолд 1 тодорхойлогчтой раунд энгийн $Div2$ раунд байх ба $6$ тодорхойлогчтой раунд $Div1$ раундтай зэрэг явагдана.

Раундуудын хамгийн их тоо нь $3$-тай тэнцүү. Энэ тохиолдолд хэрэглэгдээгүй бүх тодорхойлогч энгийн $Div2$ раундад хамаарагдана.

Сэтгэгдлүүдийг ачааллаж байна...