E. Ноён Китаюта ба хулснууд

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

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

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

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

Ноён Китаютагийн цэцэрлэг $n$ хулстай. Хулс нь хөндий голтой, хурдан ургадаг, халуун орны ургамал юм. $i$ дүгээр хулс $h_{i}$ метр өндөртэй ба өдрийн төгсгөл бүрт $a_{i}$ метрээр өндөр болдог.

Үнэндээ ноён Китаюта эдгээр хулснуудад дургүй. Тэрээр хулснуудыг тайрах гэж үзсэн боловч маш бат бөх байжээ. Гэсэн ч ноён Китаюта шантарсангүй. Тэрээр ухаанаа сийлэн хулснуудыг газарт шигтгэдэг шидэт алх урлаж гэнэ.

Түүний ид шидийн хүч хязгаарлагдмал тул шидэт алхаа өдөрт хамгийн ихдээ $k$ удаа ашиглаж чадна. Шидэт алхаар хулсыг цохих бүрт өндөр нь $p$ метрээр багасдаг. Хэрэв энэ өөрчлөлтөөр өндөр нь сөрөг утгатай болвол оронд нь $0$ метр болно (гэхдээ бүр алга болохгүй). Өөрөөр хэлбэл $h$ метрийн өндөртэй хулсыг шидэт алхаар цохивол түүний шинэ өндөр нь $max(0, h-p)$ метр болох юм. Нэг өдөрт тухайн хулсыг нэгээс олон удаа цохиж болно.

Ноён Китаюта хулснуудтай өнөөдрөөс эхлэн $m$ өдөр тэмцэнэ. Түүний зорилго нь $m$ өдрийн дараах хамгийн өндөр модны өндрийг аль болох бага байлгах юм. ("Ноён Китаюта хулснуудыг цохиод, хулс эргэж ургаад" гэх мэт $m$ өдөр үргэлжлэнэ). $m$ өдрийн дараах хамгийн өндөр модны боломжит хамгийн бага өндрийг ол.

Оролт

Эхний мөрөнд харгалзан ноён Китаютагийн цэцэрлэгдэх хулсны тоо, тэдэнтэй тэмцэх өдрийн тоо, өдөрт хэдэн удаа хулсыг цохиж болох тоо хэмжээ, шидэт алхны чадлыг илэрхийлэх $n$, $m$, $k$, $p$ тоонууд зайгаар тусгаарлагдан байна.

$(1 ≤ n ≤ 10^{5}, 1 ≤ m ≤ 5000, 1 ≤ k ≤ 10, 1 ≤ p ≤ 10^{9})$

Дараагийн $n$ мөрөнд хулснуудыг тодорхойсон байна. $i$ ($1 ≤ i ≤ n$) дэх мөрөнд $i$ дэх хулсны анхны өндөр болон ургах хурдыг илэрхийлэх $h_{i}$ ба $a_{i}$ тоонууд зайгаар тусгаарлагдсан байна.

$(0 ≤ h_{i} ≤ 10^{9}, 1 ≤ a_{i} ≤ 10^{9})$

Гаралт

$m$ өдрийн дараах хамгийн өндөр хулсны боломжит хамгийн бага өндрийг ол.

Орчуулсан: Бат-Од

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

Оролт
3 1 2 5
10 10
10 10
15 2
Гаралт
17
Оролт
2 10 10 1000000000
0 10
0 10
Гаралт
10
Оролт
5 3 3 10
9 5
9 2
4 7
9 10
3 8
Гаралт
14
Сэтгэгдлүүдийг ачааллаж байна...