题目描述

Polycarpus 所在的大公司有自己的短信服务中心（SMSC）。该中心的任务是发送各种重要信息。Polycarpus 决定检查短信服务中心的效率。

为此，他请求获得一段时间内 SMSC 的工作统计数据。最终，Polycarpus 得到了一份包含 $n$ 个任务的列表，这些任务被送往公司的 SMSC。每个任务由其被 SMSC 接收的时间和要发送的短信数量描述。更正式地，第 $i$ 个任务由两个整数 $t_{i}$ 和 $c_{i}$ 描述——接收时间（秒）和要发送的短信数量。

Polycarpus 知道，SMSC 每秒最多只能发送一条短信。SMSC 使用一个队列来组织发送。对于某个时刻 $x$，SMSC 按以下方式工作：

1. 如果在时刻 $x$ 队列非空，则 SMSC 从队首发送一条消息（此时从队首取出一条短信发送）。否则在时刻 $x$ 不发送消息。
2. 如果在时刻 $x$ 接收到某个任务，则将该任务中所有短信添加到队列的队尾。注意，在时刻 $x$ 添加到队列的短信不能在同一时刻 $x$ 被发送。因为是否发送短信的决策是在 $1$ 中添加消息之前做出的。

给定 $n$ 个任务的所有信息，Polycarpus 想知道两个数据：最后一条短信被发送的时间，以及队列在某一时刻的最大长度。请你帮助他计算这两个数据，以便他评估 SMSC 的效率。

输入格式

第一行包含一个整数 $n$ $(1 \leq n \leq 10^{3})$ —— SMSC 的任务数。接下来的 $n$ 行描述各个任务：第 $i$ 行包含两个用空格分隔的整数 $t_{i}$ 和 $c_{i}$ $(1 \leq t_{i}, c_{i} \leq 10^{6})$ ——任务被接收的时间（秒）以及该任务需要发送的短信数量。

保证所有任务的接收时刻互不相同。保证任务已按时间顺序排列，即对于所有整数 $i$ $(1 \leq i < n)$，有 $t_{i} < t_{i+1}$。

输出格式

输出两个用空格分隔的整数：最后一条短信被发送的时间，以及队列某一时刻的最大长度。

说明/提示

在第一个测试样例中：

• 第 1 秒：第一条消息进入队列，队列长度为 $1$；
• 第 2 秒：第一条消息被发送，第二条消息到达，队列长度为 $1$；
• 第 3 秒：第二条消息被发送，队列长度为 $0$。

因此，队列的最大长度为 $1$，最后一条消息在第 $3$ 秒被发送。

由 ChatGPT 5 翻译

样例

2
1 1
2 1

3 1

1
1000000 10

1000010 10

3
3 3
4 3
5 3

12 7