F. Баннерууд

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

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

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

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

Орчин үеийн бүх утасны програмууд үнэтэй болон үнэгүй гэсэн хоёр хэсэгт хуваагддаг. Тэр ч байтугай нэг програмын хөгжүүлэгч нь ихэвчлэн хоёр хувилбарыг гаргадаг: зар сурталчилгаагүй үнэтэй хувилбар, сурталчилгаатай үнэгүй хувилбар.

Програмын үнэтэй хувилбар нь $p$ ($p$ бол бүхэл тоо) рублийн үнэтэй, үнэгүй хувилбар нь $c$ зар сурталчилгаа агуулсан гэж үзье. Хэрэглэгч бүрийг хоёр бүхэл тоогоор тодорхойлсон: $a_{i}$ нь програмын үнэтэй хувилбарт хэрэглэгч төлөхөд бэлэн байгаа рублийн тоо бол $b_{i}$ нь үнэгүй хувилбарын хэрэглэгч тэсэж чадах сурталчилгааны тоо юм.

Гишүүн бүрийн зан чанарыг огт тодорхойгүй гэж үзье:

  • Хэрвээ $i$ хэрэглэгч үнэгүй хувилбарыг ашигладаг бол $b_{i}$ утга нь хамгийн багадаа $c$ байна,
  • эсрэг тохиолдолд, хэрвээ үнэтэй хувилбарыг ашигладаг бол $a_{i}$ утга нь хамгийн багадаа $p$ байна,
  • эсвэл хэрэглэгч зүгээр л програмыг ашигладаггүй.

Үнэгүй хувилбарыг ашигладаг хэрэглэгч бүр $c × w$ рублийн ашиг авчирдаг бол үнэтэй хучилбарыг ашигладаг хэрэглэгч бүр $p$ рублийн ашиг авчирдаг.

Таны даалгавар бол програмыг хөгжүүлэгчид $p$ ба $c$ параметруудыг оновчтой сонгоход нь туслах юм. Тухайлбал чи програмаас хамгийн их ашиг олоход тохирох $p$ параметрийн утгийг тодорхойлох хэрэгтэй ба бүх хэрэглэгчийн зан чанарыг мэдэж байгаа, $c$-ийн утга нь $0$-с $(max b_{i}) + 1$ байна.

Оролт

Эхний мөр нь хэрэглэгчийн тоо $n$ ба, зар сурталчилгааны тоо $w$ $(1 ≤ n ≤ 10^{5}; 1 ≤ w ≤ 10^{5})$ хоёр бүхэл тоог агуулна. Дараагийн $n$ мөр бүр нь $a_{i}$ $b_{i}$ $(0 ≤ a_{i}, b_{i} ≤ 10^{5})$ хоёр бүхэл тоог агуулна. $i$-р хэрэглэгчийн зан чанар.

Гаралт

$(max b_{i}) + 2$ мөрийг хэвлэнэ. $i$-р мөр нь хоёр бүхэл тоо агуулна: $pay$ нь хамгийн их олсон ашиг, $c = i - 1$, $p$ $(0 ≤ p ≤ 10^{9})$ -- харгалзах програмын оновчтой үнэ. Хэрвээ олон оновчтой шийдэл байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

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

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

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