在遥远的一个岛上居住着一个部落。在这个部落的人群中，共出现了 $n$ 种眼睛颜色：有 $a_i$ 个人的眼睛颜色为 $i$（$a_i > 0$），且部落不知道有其他任何颜色。更具体地，部落成员知道 $n$ 的值，但他们不知道是否所有眼睛颜色都实际存在（即他们不知道是否对所有 $i$ 都有 $a_i > 0$）。该部落信奉一种特殊的宗教：如果有人能推断出自己的眼睛颜色，他们就会在第二天自杀。需要说明的是，部落里的人都极其聪明。

在第 0 天，一位旅行者来到了这个岛上，见到了部落，并说了 $n$ 句真话，其中 $b_i \ge 0$，且至少有一个 $b_i > 0$：

• 哇，你们之中至少有 $b_1$ 个人的眼睛颜色是 1！
• 哇，你们之中至少有 $b_2$ 个人的眼睛颜色是 2！
• ...
• 哇，你们之中至少有 $b_n$ 个人的眼睛颜色是 $n$！

求发生自杀的最后一天是第几天，以及自杀的总人数。

输入格式

第一行包含一个整数 $n$（$2 \le n \le 200000$）—— 眼睛颜色的数量。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i \le 10^9$，$0 \le b_i \le a_i$，且至少有一个 $b_i > 0$）—— 眼睛颜色为 $i$ 的人数，以及旅行者所说的该人数的下界。

输出格式

输出两个整数 —— 发生自杀的最后一天（天数），以及自杀的总人数。

样例

输入样例 1

2
1 1
3 0

输出样例 1

2 4

输入样例 2

2
3 1
1 0

输出样例 2

4 4

输入样例 3

3
3 1
1 0
1 0

输出样例 3

3 3

说明

我们来解释一下第一个样例中发生了什么。

眼睛颜色为 1 的人看不到周围有任何眼睛颜色为 1 的人，但听说至少有一个人是这种颜色。因此，他们推断出自己就是这个人，并在第 1 天自杀。

所有其他人知道总共只有两种颜色，并且那个眼睛颜色为 1 的人已经死了。因此，他们推断出他们所有人的眼睛颜色都是 2，并在第 2 天自杀。