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秒发送的。