A. Өдрийн хоолны тааламж

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

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

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

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

Програмын тэмцээнтэй байхдаа $3$ туулай өдрийн хоолонд орхоор шийджээ. Дасгалжуулагч нь тэдэнд өдрийн хоолонд орох яг k хугацаа өгсөн.

Тууайнуудад өдрийн хоолонд орж болох $n$ ширхэг рестораны жагсаалт байгаа ба i дугаар рестораныг $fi$ болон $ti$ гэсэн $2$ тоогоор тодорхойлно. $ ti i $ дугаар ресторанд өдрийн хоолоо идхэд зарцуулах хугацаа. Хэрвээ $ ti $ хугацаа нь $k$ аас хэтэрвэл дасгалжуулагч нь өдрийн завсарлаганд нь хугацаа нэмж өгөх ба энэ ресторанаас $ fi - (ti - k) $ тэнцэх хэмжээний тааламжыг авна. Бусад тохиолдолд $ fi $ хэмжээний тааламжыг авна.

Таны бодлого бол ресторанаас хамаарч өдрийн хоолноосоо авч болох хамгийн их тааламжын хэмжээг олох юм. Туулайнууд өдрийн хоолондоо яг нэг ресторан сонгоно. Тааламжын хэмжээ эерэг утгатай байх албагүй.

Оролт

Эхний мөрөнд $ n (1 ≤ n ≤ 104) $ болон $ k (1 ≤ k ≤ 109) $ тоонууд зайгаар тусгаарлан өгөгдөх энэ нь туулайнуудын жагсаалтанд байгаа рестораны тоо мөн дасгалжуулчын өгсөн хугацаа. Дараагийн $n$ мөр тус бүрд i дугаар ресторыг тодорхойлох $ fi(1 ≤ fi ≤ 109) $ болон $ ti (1 ≤ ti ≤ 109) $ тоонууд зайгаар тусгаарлан өгөгдөнө.

Гаралт

Ганц мөрөнд ганц тоо байх ба энэ нь туулайнуудын өдрийн хоолноосоо авч болох хамгийн их тааламжын хэмжээ.

Орчуулсан: Gantushig

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

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