← 返回题目列表

Codeforces · 292/A

A. 短信中心

中文机器翻译题面 查看原题

Polycarpus 所在的一些大公司拥有自己的短信服务中心(SMSC)。该中心的任务是发送各种重要信息。波利卡普斯决定检查 SMSC 的效率。

为此,他要求给他一段时间内SMSC的性能统计数据。最后,Polycarpus 得到了一份包含 n 个任务的列表,这些任务被发送到公司的 SMSC。每项任务均通过 SMSC 收到任务的时间以及要发送的短信数量进行描述。更正式地说,第 i 个任务由两个整数 ti 和 ci 描述——分别是接收时间(第二个)和短信数量。

Polycarpus 知道 SMSC 每秒不能发送多于一条文本消息。 SMSC 使用队列来组织其工作。考虑一个时刻x,该时刻的SMSC工作如下:

1.如果在x时刻队列不为空,则SMSC从队列中发送一条消息(SMSC从队列头获取消息)。否则它不会在时刻 x 发送消息。
2. 如果此时 x SMSC 接收到任务,则它会将来自该任务的所有消息添加到队列中(SMSC 将消息添加到队列的尾部)。请注意,来自任务的消息无法在时间点 x 发送。这是因为是否发送消息的决定是在将这些消息添加到队列之前在第 1 点做出的。

给定所有n个任务的信息,Polycarpus想要计算两个值:发送最后一条短信的时间和某个时间队列的最大大小。帮助他计算他需要的这两个特征,以评估 SMSC 的效率。

输入

第一行包含一个整数 n (1 ≤ n ≤ 103) — SMSC 的任务数。接下来的 n 行包含任务的描述:第 i 行包含两个空格分隔的整数 ti 和 ci (1 ≤ ti, ci ≤ 106) — 接收第 i 个任务的时间(第二个)以及相应的要发送的消息数。

保证所有任务都是在不同时刻收到的。保证任务按时间顺序排序,即对于所有整数 i (1 ≤ i < n),ti < ti + 1。

输出

在一行中打印两个以空格分隔的整数 — 发送最后一条短信的时间以及特定时刻的最大队列大小。

示例

输入 #1

2
1 1
2 1

输出 #1

3 1

输入 #2

1
1000000 10

输出 #2

1000010 10

输入 #3

3
3 3
4 3
5 3

输出 #3

12 7

注意

在第一个测试样本中:

- 第二个1:第一条消息已经出现在队列中,队列的大小为1;
- 第二个2:第一条消息已发送,第二条消息已收到,队列大小为1;
- 第二个3:发送第二条消息,队列大小为0,

因此,队列的最大大小为1,最后一条消息是在第3秒发送的。