A. SMSC

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

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

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

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

Поликарпусийн ажилладаг том корпораци өөрийн богино мэссэжийн үйлчилгээний төвтэй (SMSC). Төвийн ажил бол бүх төрлийн чухал мэдээллийг илгээх юм. Поликарпус SMSC-н үр ашгийг шалгахаар шийдсэн.

Үүний тулд тэр хэсэг хугацаан дахь SMSC-н гүйцэтгэлийн статистикийг түүнд өгөхийг хүссэн. Эцэст нь Поликарпус корпорацийн SMSC-рүү илгээгдсэн $n$ ажил бүхий жагсаалтыг авсан. Ажил бүр SMSC-н хүлээн авсан цаг болон илгээх текст мэссэжийн тоогоор тодорхойлогдоно. Илүү тодорхой хэлбэл $i$-р ажил нь $t_{i}$ ба $c_{i}$ буюу харгалзан хүлээн авсан цаг (секундээр) болон текст мэссэжийн тоогоор тодорхойлогодоно.

Поликарпус SMSC нь секундэд нэгээс олон мэссэж явуулж чадахгүй гэдгийг мэднэ. SMSC нь ажлаа зохион байгуулахдаа дараалал ашигладаг. $x$ мөч дахь SMSC-н ажиллагааг авч үзье:

  1. Хэрвээ $x$ мөчид дараалал хоосон биш байвал SMSC дарааллаас нэг текст мэссэж явуулна (мэссэжийг дарааллын толгойгоос авна). Бусад тохиолдолд SMSC нь $x$ мөчид мэссэж явуулахгүй.
  2. Хэрвээ $x$ мөчид SMSC нь ажил хүлээн авбал дараалалруу уг ажлын бүх мэссэжийг нэмнэ (SMSC мэссэжүүдийг дарааллын сүүлд нэмнэ). Уг ажлын мэссэжүүдийг $x$ мөчид явуулах боломжгүйг санаарай. Учир нь мэссэж явуулах эсэх нь дараалалд мэссэжүүдийг нэмэхээс өмнө 1 цэг дээр шийдэгддэг.

Өгөгдсөн $n$ ажлуудын мэдээллээс Поликарпус хоёр утгыг тоолохыг хүсч байна: сүүлийн текст мэссэж илгээгдсэн хугацаа болон дарааллын хамгийн их хэмжээ. Түүнд SMSC-н үр ашгийг үнэлэхэд хэрэгтэй энэ хоёр утгыг тоолоход туслана уу.

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ $(1 ≤ n ≤ 10^{3})$ байх ба SMSC-н ажлуудын тоо юм. Дараагийн $n$ мөрөнд ажлуудыг тодорхойлох ба $i$-р мөрөнд зайгаар тусгаарлагдсан хоёр бүхэл тоо $t_{i}$ ба $c_{i}$ $(1 ≤ t_{i}, c_{i} ≤ 10^{6})$ байх ба харгалзан $i$-р ажлыг хүлээн авсан хугацаа болон илгээх мэссэжүүдийн тоо байна.

Бүх ажлууд хугацааны ялгаатай мөчүүдэд ирсэн. Ажлууд ирсэн хугацаагаараа эрэмбэлэгдэх буюу бүх $i$ $(1 ≤ i < n)$ бүхэл тооны хувьд $t_{i} < t_{i + 1}$ байна.

Гаралт

Нэг мөрөнд сүүлийн мэссэж явсан хугацаа болон хугацааны тухайн нэг агшинд дарааллын хамгийн их хэмжээг илэрхийлэх хоёр бүхэл тоог нэг мөрөнд хэвлэ.

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

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

Оролт
2
1 1
2 1
Гаралт
3 1
Оролт
1
1000000 10
Гаралт
1000010 10
Оролт
3
3 3
4 3
5 3
Гаралт
12 7

Тэмдэглэл

Эхний жишээн дээр:

  • 1 дахь секунд: дараалалд эхний мэссэж орно, дарааллын хэмжээ 1;
  • 2 дахь секунд: эхний мэссэж илгээгдсэн, хоёр дахь мэссэжийг хүлээн авсан, дарааллын хэмжээ 1;
  • 3 дахь секунд: хоёр дахь мэссэж илгээгдсэн, дарааллын хэмжээ 0.

Иймээс дарааллын хамгийн их хэмжээ 1, сүүлийн мэссэж 3 дахь секундэд илгээгдсэн.

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