E. Гар Утасны яриа

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

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

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

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

Күүл Жи саяхнаас бизнесмэн болсон бөгөөд өөрийгөө Ноён Жэксон гэх болжээ. Одоо тэрээр маш олон гар утасны дуудлага хийдэг болсон байна. Өнөөдөр түүнд төлөвлөсөн $n$ ширхэг дуудлага байв. Дуудлага бүрийн хувьд бид $t_{i}$ (уг өдөр эхэлснээс хойших өнгөрсөн секундийн тоо) буюу уг дуудлага эхлэхээр төлөвлөгдсөн хугацаа болон уг дуудлага үргэлжлэх хугацаа $d_{i}$ (секундээр)-ыг мэдэж байх юм. Бүх $t_{i}$-ууд нь ялгаатай байх бөгөөд ноён Жэксон өөрөө маш чухал хүн учраас хэзээ ч бусад хүмүүс уруу залгадаггүй байв. Харин хүмүүс түүн уруу залгадаг бөгөөд өөрөөр хэлбэл түүний хийж буй бүх дуудлага нь ирж буй дуудлагууд байх юм.

Ноён Жэксон Цезар биш учраас тэрээр нэгэн зэрэг хэд хэдэн зүйлсийг хийж чадахгүй. Хэрэв тэрээр өмнөх яриагаа дуусгаагүй байхад өөр хэн нэгэн түүн уруу залгавал ноён Жэксон шинээр ирж буй дуудлагыг хүлээлгийн горимд тавих юм. Уг тохиолдолд ноён Жэксон одоо ярьж буй яриагаа дуусмагц шууд араас нь хүлээлгийн горимд хамгийн түрүүнд ирсэн дуудлагыг авч яриаг эхлүүлнэ. Хэрэв ноён Жэксон дуудлагаа $t$ секунд дээр эхлүүлсэн ба $d$ секундийн турш ярьсан байвал ноён Жэксон $t, t + 1, ..., t + d - 1$ гэсэн секунд-д завгүй байна гэж үзэх бөгөөд шинэ дуудлагаа $t + d$ секундээс эхлүүлнэ гэж үзнэ. Хэрэв ноён Жэксон хэн нэг залгах үед ярих завгүй биш байвал тэрээр уг дуудлагыг хүлээлгийн горимд тавьж болохгүй болохыг анхаарна уу.

Ноён Жэксон Наполеон ч биш учраас тэрээр унтах дуртай ажээ. Иймд заримдаа тэрээр өөртөө зарим дуудлагыг үл тоох эрх олгодог ба тодруулбал уг дуудлага төлөвлөгөөнд огт байгаагүй мэтээр төлөвлөгөөнөөс хасагдах юм. Тэрээр хамгийн ихдээ $k$ ширхэг дуудлага үл тоож болно. Тэрээр завгүй ярьж байх зуур ирсэн дуудлагыг мөн үл тоож болохыг анхаарна уу.

Тэрээр утсаар завгүй яриагүй байх үедээ хугацааны тасралтгүй нэгэн сегментийг сонгон унтаж болно гэж үзээд ноён Жэксоны өнөөдөр (энэ нь 1-дэх секундээс 86400-дэх секунд хүртэлх хугацаа юм) унтаж болох хамгийн их секундийн тоог олно уу

Зарим дуудлагууд нь дараагийн өдөр уруу эсвэл бүр өөр өдөр хүртэл хойшлогдож эсвэл үргэлжилж болохыг анхаарна уу. Энэ нь зарим дуудлагууд нь 2 өдрийн турш үргэлжилж болно гэсэн үг юм. Тэгсэн хэдий ч ноён Жэксоны унтах интервал нь тухайн өдөр дотроо байх ёстойг анхаарна уу.

Оролт

Эхний мөрөнд хос бүхэл тоо $n$, $k$ ($0 ≤ k ≤ n ≤ 4000$) зайгаар тусгаарлагдан өгөгдөнө. Дараагийн $n$ мөрөнд өнөөдөр төлөвлөгдсөн бүх дуудлагуудын тайлбар өгөгдөнө. Дуудлага бүрийн тайлбар нь дан мөрөнд тодорхойлогдох бөгөөд зайгаар тусгаарлагдсан 2 бүхэл тоо $t_{i}$ болон $d_{i}$ ($1 ≤ t_{i}, d_{i} ≤ 86400$)-аас тогтох юм. Бүх $t_{i}$-ууд нь ялгаатай байх бөгөөд дуудлагууд нь $t_{i}$-ын ихсэх дарааллын дагуу өгөгдсөн байна.

Дуудлагуудын үргэлжлэх хугацаа [$t_{i}$, $t_{i} + d_{i} - 1$]-ууд нь дурын байдлаар огтлолцсон байж болно.

Гаралт

0-ээс 86400 хүртэлх (эдгээр тоонууд нь мөн орно) нэгэн тоог хэвлэх ба энэ нь ноён Жэксоны өнөөдөр унтах боломжит хамгийн их секундийн тоог илэрхийлнэ.

Орчуулсан: Баатархүү

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

Оролт
3 2
30000 15000
40000 15000
50000 15000
Гаралт
49999
Оролт
5 1
1 20000
10000 10000
20000 20000
25000 10000
80000 60000
Гаралт
39999

Тэмдэглэл

Эхний жишээнд хамгийн тохиромжтой арга нь эхний 2 дуудлагыг үл тоох юм.

2-дахь жишээнд 3-р дуудлагыг үл тоох нь хамгийн зөв арга байна. Уг тохиолдолд ноён Жэксон дараах байдлаар утсаар ярина:

  • эхний дуудлага: 1-р секундээс 20000-р секунд хүртэл,
  • 2-дахь дуудлага: 20001-р секундээс 30000-р секунд хүртэл,
  • 4-дэх дуудлага: 30001-р секундээс 40000-р секунд хүртэл(3-р дуудлагыг үл тооно),
  • 5-дахь дуудлага: 80000-р секундээс 139999-р секунд хүртэл.

Иймд зав чөлөөтэй байх хамгийн урт үе нь 40001-р секундээс 79999-р секунд хүртэл байна.

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