B. Валера ба жимснүүд

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

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

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

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

Валера-гийн хайртай цэцэрлэгт $n$ жимсний мод ургадаг.

Энэ жил тэр маш их ургац авна! $i$-р модонд $b_{i}$ жимс ургасан, тэдгээрээс өдөрт $a_{i}$ жимс боловсордог. Харамсалтай нь модны жимс хатсан, иймээс эдгээрээс эхний өдөр $a_{i}$, дараагийн өдөр $a_{i} + 1$ жимс цуглуулсан (Эдгээр хоёр өдөрт бүх жимсийг цуглуулаагүй зарим нь идэх тохиромжгүй байсан).

Валера хурдан биш гэхдээ түүнд зарим нэг сайн талууд байдаг. Валера өдөр бүр ажилдаа бэлэн байдаг. Нэг өдөр Валера $v$-ээс ихгүй жимс цуглуулсан. Жимс ижил модонд эсвэл өөр нэгд байж магадгүй. Хэрвээ Валера оновтой сайн ажиллаж цуглуулж чадах жимсний хамгийн их тоо хэд вэ?

Оролт

Эхний мөр нь зайгаар тусгаарлагдсан бүхэл $n$, $v$ $(1 ≤ n, v ≤ 3000)$ тоонуудыг агуулна. Эдгээр тоо нь цэцэрлэгийн жимсний модны тоо, Валера-гийн нэг өдөрт цуглуулж чадах жимсний тоо.

Дараагийн $n$ мөр нь цэцэрлэгийн моднуудын тодорхойлолтыг агуулна. $i$-ээр мөр нь зайгаар тусгаарлагдсан бүхэл $a_{i}$ болон $b_{i}$ $(1 ≤ a_{i}, b_{i} ≤ 3000)$ тоонуудыг агуулна. $a_{i}$ нь $i$-ээр модны тухайн өдөрт боловсорсон жимсний тоо, $b_{i}$ нь $i$-ээр модны нийт жимсний тоо юмаа.

Гаралт

Валера-гийн түүж чадах жимсний хамгийн их тоог бүхэл хэвлэнэ.

Орчуулсан: Даариймаа

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

Оролт
2 3
1 5
2 3
Гаралт
8
Оролт
5 10
3 20
2 20
1 20
4 20
5 20
Гаралт
60

Тэмдэглэл

Эхний жишээнд оновчтой хариулт авахын тулд дараах үйлдлүүдийг дагаарай.

  • Эхний өдөр $1$-р модноос $3$ жимс түүнэ.
  • Хоёр дахь өдөр $2$-р модноос $1$ жимс, $1$-р модноос $2$ жимс түүнэ.
  • Гурав дахь өдөр $2$-р модноос үлдсэн жимснүүдийг түүнэ.

Хоёр дугаар жишээнд та зөвхөн $60$ жимс түүнэ, үлдсэн жимс нь хатсан.

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