Даалгавар ба дуусгах хугацаа

2s

512MB

1203

0%

Sorting and Searching

$n$ даалгавар гүйцэтгэнэ. Даалгавар бүр үргэлжлэх хугацаа болон дуусгах хугацаатай бөгөөд даалгавруудыг ямар нэг дарааллаар нэг нэгээр нь гүйцэтгэнэ. Даалгаврын шагнал нь $d-f$ бөгөөд $d$ нь дуусгах хугацаа, $f$ нь даалгаврыг дуусгах цаг. (Эхлэх цаг $0$ , шагнал сөрөг гарсан ч бүх даалгаврыг гүйцэтгэнэ.)

Оновчтой ажилбал авах шагналын хамгийн их утгыг ол.

Эх сурвалж: cses.fi

Оролтын формат

Эхний мөрөнд $n$ бүхэл тоо байна: даалгаврын тоо.

Дараа нь даалгавруудыг тодорхойлсон $n$ мөр байна. Мөр бүрт хоёр бүхэл тоо $a$ ба $d$ байна: даалгаврын үргэлжлэх хугацаа болон дуусгах хугацаа.

Гаралтын формат

Нэг бүхэл тоо хэвлэ: хамгийн их шагнал.

Хязгаарлалт

$1 \le n \le 2 \cdot 10^5$
$1 \le a,d \le 10^6$

Жишээ

Оролт1

Гаралт1

0.1 / 64 KiB

Редактор уншиж байна...