No.904 サメトロ

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 87
作問者 : pekempeypekempey / テスター : cielciel
7 ProblemId : 2699 / 出題時の順位表

問題文

yuki 国には駅が $N$ 駅あり $1$ から $N$ の通し番号がついています。この $N$ 駅同士は改札を出ずに行き来できる電車があり、この $N$ 駅とそれ以外の駅を行き来できる電車はありません。この国の駅には改札を入ったら入った駅とは異なる駅の改札を出なければならないという規則があります。さらにこの国では夜に駅が閉まるため、改札を入ったらその日中に改札を出なければなりません。

これらの駅では改札を入った人数と改札を出た人数を毎日記録しているのですが、yuki 国のとあるお祭りの日に起きたとある事件の影響でこの日だけ駅 $1$ に関する記録が残っていません。お祭りの日に駅 $i$ に入った人数を $A_i$、出た人数を $B_i$ とするとき $(A_1, B_1)$ が何通りあり得るのか求めてください。

入力

$N$
$A_2\;B_2$
$A_3\;B_3$
$\vdots$
$A_N\;B_N$

$2 \le N \le 37$
$0 \le A_i, B_i \le 10000\quad(2 \le i \le N)$

出力

答えを出力してください。答えは有限の値であることが示せます。

サンプル

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

ありえる組は $(A_1,B_1)=(0,4),(1,5),(2,6),(3,7)$ です。たとえば $(A_1,B_1)=(0,4)$ は以下の状況が考えられます。

  • 人 $1$ が駅 $2$ で入って駅 $1$ で出た。
  • 人 $2$ が駅 $2$ で入って駅 $1$ で出た。
  • 人 $3$ が駅 $2$ で入って駅 $3$ で出た。
  • 人 $4$ が駅 $3$ で入って駅 $1$ で出た。
  • 人 $5$ が駅 $3$ で入って駅 $1$ で出た。
  • 人 $6$ が駅 $3$ で入って駅 $2$ で出た。
  • 人 $7$ が駅 $3$ で入って駅 $2$ で出た。
サンプル2
入力
4
3 3
3 3
2 2
出力
9

サンプル3
入力
3
10000 10000
10000 10000
出力
20001

$A_1$, $B_1$ は $10000$ を超えても構いません。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。