問題
在 CAT 国,今天举行了议会的全国选举。CAT 国的选举采用仅按比例代表制的特殊形式,议席根据得票数按最大余数法分配。也就是说, n 每个共有的政党得票数为 a_1, a_2, ..., a_n,总票数为 s = a_1 + a_2 + ... + a_n,总议席数为 m ,首先每个政党分配 [\frac{a_i}{s}m] 个议席,剩余的议席将按 \frac{a_i}{s}m 的小数部分从大到小依次分配给政党(同分时优先编号较小的政党),每次分配 1 个议席。此处,[x]是小数x的整数部分。
住在 CAT 国的你当然去投了票,现在正在和朋友在聊天中讨论选举结果。朋友告诉你如下信息:
- 各党分别 a_1, a_2, ..., a_n 获得了票数。
- 各党至少 b_1, b_2, ..., b_n 获得了议席。
如果他的信息是正确的,求总议席数 m 可能值中的最小值。
入力
n a_1 b_1 ... a_n b_n
第 1 行为政党数 n 。 继续 关键信息在 n 行中, i 第 i 个政党的得票数 a_i, i 第 i 个政党至少获得的议席数 b_i 按此顺序给出。
出力
满足条件的总议席数 m 的最小值输出为 1 行。
制約
- 1 \leq n \leq 100
- 1 \leq a_i \leq 1000
- 0 \leq b_i \leq 10^9
- b_i \geq 1实现i存在。
部分点
针对该问题的判断设置了一组50分的测试用例。该组中包含的测试用例输入还满足以下条件。
n, a_i, b_i \leq 50
入力例 1
3 1 2 4 5 2 3
输入示例 1 的输出示例
11
入力例 2
4 1 0 6 5 4 4 5 8
输入示例 2 的输出示例
25
入力例 3
1 42 42
输入示例 3 的输出示例 一直到
42