← 返回题目列表

AtCoder · utpc2012_05

E. 选举

中文机器翻译题面 查看原题

問題

在 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