题目描述

学校一共有 $n$ 个班级，其中每个班级的编号分别为 $1\sim n$，第 $i$ 个班级有 $w_i$ 名学生。

众所周知由于有时差的关系，当世界时间 (UTC) 处于 $0$ 点的时候，第 $i$ 个班级的时间是 $x_i$ 点。

现在你想召开一次一小时的会议，每个学生只能在 $9:00\sim 18:00$ 的时间段内参加会议，请你选择合适的会议时间，使得可以参加的学生人数最多。

请输出这个最多的参加人数

输入格式

第一行输入一个数字 $n$，代表有 $n$ 个班级。

接下来 $n$ 行，每行两个整数分别为 $w_i$ 和 $x_i$ 含义分别为第 $i$ 个班级的学生人数和当世界时间 (UTC) 处于 $0$ 点的时候，当前班级的时间是 $x_i$ 点。

输出格式

输出可以参加会议的最大学生数量

3
5 0
3 3
2 18

8

2
1 10
1000000 20

1000000

6
31 3
20 8
11 5
4 3
47 14
1 18

67

提示

样例一解释

当我们选择在世界时间 $14:00\sim 15:00$ 开这个会议的时候。

• 对于第一个班级来说，它的 $x_i$ 是 $0$，此时的时间就是 $14:00\sim 15:00$ 因此 $5$ 个人都可以来参加会议。
• 对于第二个班级来说，它的 $x_i$ 是 $3$，此时的时间就是 $17:00\sim 18:00$ 因此 $3$ 个人都可以来参加会议。
• 对于第三个班级来说，它的 $x_i$ 是 $18$，此时的时间就是 $8:00\sim 9:00$，由于每个学生只能在 $9:00\sim 18:00$ 的时间段内参加会议，因此第三个班级的学生无法参加会议。 可以证明不会有其他的时间段可以使得参加人数超过 $8$。