E. Жигнэмэг дарагч

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

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

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

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

Костя Жинэмэг дарагч хэмээх компьютерийн тоглоом тоглож байна. Тоглоомын зорилго нь жигнэмэгүүдийг цуглуулах юм. Та өөр өөр барилгуудаар жигнэмэг олж болно. Та талбайн онцгой хэсэгт дарснаараа жигнэмэг авна. Мөн та жигнэмэгний үйлдвэр, алхимийн лаборатори, болон цаг хугацааны машин худалдана авч болно. Эдгээр нь танд маш их жигнэмэг авч ирнэ.

Тоглоом эхлэхэд (0 цагт) Костяд $0$ жинэмэг байсан ба түүнд ямар ч барилга байгаагүй. Түүнд $n$ янзын боломжит барилга байгаа ба $i$-дэх барилга нь $c_i$ үнэтэй ба секунт бүр $v_i$ жигнэмэг гаргадаг. Тоглоомыг сонирхолтой болгох үүднээс Костя нэг мөчид нэг л барилга ашиглахаар шийджээ. Мэдээж тэрээр секунт бүрт идэвхтэй байх барилгыг өөрийн дураар сонгоно.

Костя энэхүү тоглоомыг тоглож байхдаа нэг секунтанд хэд хэдэн барилга худалдаж авах болон идэвхтэй барилгыг хэд хэдэн удаа өөрчилж болно. Костя шинэ барилга худалдан авмагцаа ашиглаж чаддаг. Энэ нь тоглоомын $t$ агшинд худалдан авагдсан барилга $t+1$ дэх агшинд ашгаа өгч эхэлнэ гэсэн үг.

Костя аль болох хурдан хугацаанд ядаж $s$ жигнэмэг цуглуулахыг хүсэж байна. Түүнд хэдэн секунь хэрэгтэй болохыг тодорхойл.

Оролт

Эхний мөрөнд $n$ ба $s$ $(1\ ≤\ n\ ≤\ 2·10^5,\ 1\ ≤\ s\ ≤\ 10^{16})$ өгөгдөнө. Дараагийн $n$ мөрөнд $i$-р барилга секунтанд гаргаж чадах жигнэмэгний тоо $v_i\ (1\ ≤\ v_i\ ≤\ 10^8)$ болон барилгын үнэ $c_i\ 0\ ≤\ c_i\ ≤\ 10^8$ байрлана.

Гаралт

Шаардлагатай хамгийн бага хугацааг хэвлэнэ. Костя үүнийг баталгаатай хийж чадна.

Орчуулсан: Говьхүү

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

Оролт
3 9
1 0
2 3
5 4
Гаралт
6
Оролт
3 6
1 0
2 2
5 4
Гаралт
5
Оролт
3 13
1 0
2 2
6 5
Гаралт
7
Оролт
1 10000000000000000
1 0
Гаралт
10000000000000000
Сэтгэгдлүүдийг ачааллаж байна...