B. Ачааны тэрэг

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

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

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

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

Хэсэг жуулчид каяак болон катамаран завиар аялал хийх гэж байна. Энэ үед хөлсөлж авсан ачааны тэрэг завинуудыг жуулчдад аваачиж өгөхөөр боомт дээр иржээ. Бүх каяак завь ижил эзэлхүүнтэй (бүгд $1 м^3$), ба бүх катамаран завь ч бас ижил эзэлхүүнтэй (бүгд $2 м^3$)

Бүх завь ижил эзэлхүүнтэй ч гэсэн өөр өөрийн ялгаатай багтаамжтай. Завины зогсоол дээр байгаа бүх завины төрөл ба багтаамж өгөгдсөн бол ачааны тэргэнд багтааж болохоор хамгийн олон хүний багтаамжтай байхаар завинуудыг сонгоорой. Ачааны тэргэнд бүрэн ачилт хийж болдог гэж үзнэ.

Оролт

Оролтын эхний мөрөнд зогсоолд байгаа завины тоо $n$ ба ачааны тэрэгний багтаамж $v$ өгөгдөнө. ($1 ≤ n ≤ 10^5$; $1 ≤ v ≤ 10^9$). Дараагийн $n$ мөр завины мэдээллийг агуулах бөгөөд мөр тус бүр завины төрөл $t_i$ ба багтаамж $p_i$-с тогтоно ($1 ≤ t_i ≤ 2$; $1 ≤ p_i ≤ 10^4$). Энд $t_i$ нь $1$ бол каяак, $2$ бол катамаран гэж үзээрэй. Завинуудыг оролтонд өгсөн дарааллаар дугаарлана.

Гаралт

Эхний мөрөнд хамгийн их боломжит багтаамжийг гаргана. Хоёр дахь мөрөнд сонгож авах завинуудын дугаарыг хэвлэнэ. Хэрвээ олон боломжит хариу байвал алийг нь ч гаргаж болно.

Орчуулсан: zoloogg

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

Оролт
3 2
1 2
2 7
1 3
Гаралт
7
2
Сэтгэгдлүүдийг ачааллаж байна...