时间限制：1秒　　内存限制：256M

---

【题目描述】

　　开学了，学校要求你进行入学体检。

　　你到了校医务室门口，发现有好多学生在排队，人数还在不断增加。

　　有多个体检项目要做。每个项目都有很多人在排队。队伍的长度在随着时间变长。该选哪一个队伍排队呢？这成了一个问题。你要安排一下体检顺序，尽可能早的完成所有项目的体检。

【输入格式】

　　第一行一个整数 \(n\)，表示要体检的项目数量。
　　接下来 \(n\) 行，每行表示一个体检项目。每行两个整数 \(a\) 和 \(b\)，描述该项目的情况：
　　　1.如果你在第 0 时刻加入了这只队伍（即第一个加入这个队伍），则需要 \(a\) 秒钟才能完成该项目的检查。
　　　2.当你不在这个队伍里，随时间队伍会变得越来越长，等待的时间每秒钟会增加 \(b\) 秒，即如果你在第 \(t\) 秒末加入这个项目的队伍，则需要等待 \(t×b\) 秒，然后再用 \(a\) 秒完成该项目的体检，即 \(t×b+a\) 秒末才能完成该项目的体检。

【输出格式】

　　一个整数表示你完成体检最短需要花费的时间。结果可能很大，所以请 mod (365×24×60×60) 再打印出结果

【输入输出样例1】

　Input

5
4 5
1 2
3 4
5 6
2 3

　Output

1419

【输入输出样例1解释】

　　你按照 2，5，3，1，4 的顺序来体检，花费的总时间计算如下：
　　1.在第 2 个体检项目的队伍中花了 1 秒；
　　2.在第 5 个体检项目的队伍中花了 1×3+2=5 秒，即在第 6 秒末体检完这个项目；
　　3.在第 3 个体检项目的队伍中花了 4×6+3=27 秒，即在第 33 秒末体检完这个项目；
　　4.在第 1 个体检项目的队伍中花了 5×33+4=169 秒，即在第 202 秒末体检完这个项目；
　　5.在第 4 个体检项目的队伍中花了 6×302+5=1217 秒，即在第 1419 秒末体检完这个项目；
　　所以总时间是 1419 秒。

【输入输出样例2】

　Input

7
5 2
2 27
9 5
7 16
2 3
14 10
13 9

　Output

331466

【数据限制】

　　对于 \(50\%\) 的数据，\(1≤n≤1000\)，\(0≤a,b≤30000\)。
　　对于 \(100\%\) 的数据，\(1≤n≤100000\)，\(0≤a,b≤50000\)。

【来源】

　　Mr.he