No.180 美しいWhitespace (2)
ぴろず問題文
太郎君の弟の次郎君は難解プログラミング言語である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もしくは右上の雲マークをクリックしてアカウントを作成してください。