No.180 美しいWhitespace (2)

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 87
作問者 : ぴろずぴろず
15 ProblemId : 425 / 出題時の順位表
問題文最終更新日: 2015-11-14 17:48:27

問題文

太郎君の弟の次郎君は難解プログラミング言語であるWhitespaceで美しいプログラムを書くことに熱中しています。
Whitespaceでは、スペース・タブ・改行のみを構文に使用し、その他は無視します。

太郎君はソースコードに全角スペースを混ぜていましたが、次郎君はそれだとインタプリタによってはエラーになることに気が付きました。
次郎君は$N$行からなるソースコードを書きました。$i$行目にはスペースが$a_i$個、タブが$b_i$個含まれます。ソースコードにスペース・タブ・改行以外の文字は含まれません。

次郎君はエディターのタブ幅$x(x$は正の整数$)$を変えることによって、ソースコードの「醜さ」を最小にしようとしています。
ソースコードの「醜さ」は、ソースコードの行の幅の最大値から最小値を引いたものです。
より正確に言うと、タブ幅$x(x$は正の整数$)$に対して、「醜さ」$f(x)$は次の式で与えられます。
$\displaystyle f(x) = \left( \max_{1 \leq i \leq N} (a_i + b_ix) \right) - \left( \min_{1 \leq i \leq N} (a_i + b_ix) \right)$
普通のエディタとは異なり、タブの位置などは幅に影響せず、スペースとタブそれぞれの個数のみから「醜さ」が決まることに注意してください。

ソースコードの「醜さ」$f(x)$を最小にする正の整数$x$のうち、最も小さいものを出力するプログラムを作成してください。

入力

$N$
$a_1$ $b_1$
$\vdots$
$a_N$ $b_N$
$1$行目に次郎君が書いたソースコードの行数$N$が与えられます。
続く$N$行は、ソースコードの行ごとの情報です。$i$行目にはスペースが$a_i$個、タブが$b_i$個あることを表します。

$1 \leq N \leq 1000$
$0 \leq a_i, b_i \leq 10^9$
次郎君のソースコードにはスペース・タブ・改行以外の文字は含まれません。
次郎君のソースコードがWhitespaceの文法的に正しいとは限りません。

出力

ソースコードの「醜さ」$f(x)$を最小にする正の整数$x$のうち、最も小さいものを出力してください。 最後に改行してください。

サンプル

サンプル1
入力
2
1 1
3 0
出力
2

$1$行目にはスペースが$1$個、タブが$1$個あります。
$2$行目にはスペースが$3$個、タブが$0$個あります。
タブ幅を$2$にすると、$1$行目の幅が$1 + 1 \times 2 = 3$、$2$行目の幅が$3 + 0 \times 2 = 3$となり、「醜さ」は0になります。
また、「醜さ」を0にするタブ幅は$2$のみであることがわかるので、$2$を出力します。

サンプル2
入力
4
0 0
0 0
0 0
0 0
出力
1

$4$行全てが空行です。
この場合任意の$x(\geq 1)$に対して$f(x)=0$です。
$f(x)$を最小にする$x$のうち最小のものを出力するので、$1$を出力します。

サンプル3
入力
2
1 4
9 1
出力
3

$f(x)$が最小値をとるのは$x = 3$のときのみで、このとき$f(x) = 13 - 12 = 1$です。

サンプル4
入力
10
4321123 46
9506183 4
2469242 61
1111211 72
1234721 71
3333474 54
1111260 72
123559 80
1728545 67
7407433 21
出力
123456

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。