No.146 試験監督(1)

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 128 MB / 通常問題
タグ : / 解いたユーザー数 217
作問者 : LayCurseLayCurse

4 ProblemId : 369 / 出題時の順位表

問題文

とある教員(匿名希望)は,すぐ近くでは節分祭をやっている中,期末試験の試験監督をしている時に以下の問題を考えました.

カンニング防止の為,受講生は同じ机で隣同士の席に座ることはできません.
例えば,$3$ つの椅子がある机の場合,$2$ 人の受講生が座る場合は両端の椅子を使う以外は許されておらず,$1$ 人の受講生が座る場合は $3$ つのうちどの椅子でも使うことができます.
ある部屋では,$N$ 種類の机があり,$C_k$ 個の椅子がある机が $D_k$ 個あります.
ここで,$C_k$ 個の椅子がある机は,$C_k$ 個の椅子が直線上に配置されています.
この部屋で試験を受けることができるの受講生の人数の最大値を ${\rm mod}\ 10^9+7$ で求めるプログラムを書いてください.


図1.この問題が生まれた場所(京都大学1共01教室,2015年2月4日)

入力

$N$
$C_1$ $D_1$
$C_2$ $D_2$
$\vdots$
$C_N$ $D_N$

$1 \leq N \leq 100000 = 10^5$
$1 \leq C_k \leq 10^{18}$
$1 \leq D_k \leq 10^{18}$
$i \neq j$ のとき $C_i \neq C_j$

出力

この部屋で試験を受けることができるの受講生の人数の最大値を ${\rm mod}\ 10^9+7$ で出力して下さい.

サンプル

サンプル1
入力
2
2 5
3 20
出力
45

写真の教室の場合です.
2つの椅子のある机には最大1人,3つの椅子のある机には最大2人が座れるので,合計で45人まで試験を受けることができます.

提出ページヘ