G. Ажилд авах

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

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

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

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

Хүний нөөцийн хэлтсийн дарга шинэ ажилчин хөлслөхөөр шийдсэн. Тэр нэр дэвшигчдэд зориулж хамгийн ихдээ $m$ ажлын өдөрт багтааж хийх ёстой жишээ дасгал бэлдсэн. Нэр дэвшигч бүр уг дасгалыг давах ёстой. $j$-р өдөрт нэр дэвшигч оффис дээр хамгийн ихдээ $t_{j}$ нэгж хугацаанд байхыг зөвшөөрнө.

Нийтдээ $n$ нэр дэвшигч уг ажлын байр дээр нэрээ өгөхөөр шийдсэн ба өөрсдийн анкетаа ирүүлсэн. Ирсэн мэдээлэл дээр үндэслээд дарга нэр дэвшигч бүрийг тодорхойлох хоёр параметр тодорхойлж байна: $d_{i}$ ба $r_{i}$. Параметр $d_{i}$ нь $i$-р нэр дэвшигч өглөө бүр ажилдаа бэлдэх хугацаа юм. Энэ цаг нь өдрөөс хамаарахгүй. Параметр $r_{i}$ нь $i$-р ажилчин жишээ дасгалыг бүхэлд нь гүйцэтгэхэд шаардлагатай ажиллах хугацаа байна.

Иймээс $j$-р өдөр оффист өнгөрүүлсэн хугацаа нь бэлдсэн $d_{i}$ хугацааны нэгж болон дасгалыг хийсэн хэсэг хугацаанаас бүрдэнэ. Нэр дэвшигч ажлын өдрийг бүхэлд нь алгасаж болох ба оффис дээр ирэхгүй байж болно. Мэдээж энэ тохиолдолд тэр ажлын бэлтгэлд $d_{i}$ нэгж хугацаа зарцуулахгүй.

Дасгалыг гүйцээхийн тулд нэр дэвшигч яг $r_{i}$ нэгж хугацаа (ажилд бэлдэх хугацааг энд тооцохгүй) зарцуулах ёстой.

Нэр дэвшигч бүрийн хувьд тэр дасгалыг бүрэн дуусгаж чадах хамгийн эрт өдрийг олно уу. Ажлын өдрийг алгасахыг зөвшөөрөх боловч хэрвээ нэр дэвшигч уг өдөр ажиллах бол дасгалын өмнө заавал ажилдаа бэлдэн $d_{i}$ нэгж хугацаа зарцуулах ёстой.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $n,  m$ $(1 ≤ n,  m ≤ 2*10^{5})$ байх буюу нэр дэвшигчдийн тоо болон жишээ дасгалыг хийх ажлын өдрийн хамгийн их тоо юм.

Хоёр дахь мөрөнд $m$ бүхэл тоон утга $t_{1}, t_{2}, ..., t_{m}$ $(1 ≤ t_{j} ≤ 10^{6})$ байх буюу ажлын өдрүүдийн урт хугацааны нэгжээр өгөгдөнө.

Дараагийн $n$ мөр бүрт хоёр бүхэл тоо: $d_{i},  r_{i}$ $(0 ≤ d_{i} ≤ 10^{6},  1 ≤ r_{i} ≤ 10^{6})$ байх ба $i$-р дэвшигчийн ажлаа эхлэхээс өмнө шаардлагатай хугацаа болон ажлыг гүйцэтгэхэд шаардлагатай хугацаа байна.

Гаралт

$n$ бүхэл тооны $b_{1}, b_{2}, ..., b_{n}$ хэвлэх ба энд $b_{i}$ нь $i$-р дэвшигч жишээ дасгалыг дуусгаж чадах хамгийн эрт өдөр байна.

Хэрвээ $i$-р дэвшигч жишээ дасгалаа $m$ өдөрт багтааж дуусгаж чадахгүй бол $b_{i} = 0$ байна.

Энэ бодлогон дахь өдрүүд оролтонд өгсөн дарааллаараа 1-c эхлэн $m$ хүртэл дугаарлагдана.

Орчуулсан: Г.Мэндбаяр

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

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