Tunnel

Time Limit : 8 sec, Memory Limit : 65536 KB

問題 1


 n 分間にわたり, トンネルの入口と出口で, 1分間に通過する車の数を数えたデータがある. そのデータは, 全部で n+2 行からなり, 各行には次の内容が書かれている.

  • 第1行目には,正整数 n が書かれており, 調査時間が n 分間であったことを表している.
  • 第2行目には,正整数 m が書かれており, 調査開始時におけるトンネル内の車の台数が m であったことを表している.
  • 第(2+i)行目( i = 1, 2, ... , n ) には, 調査開始後 (i-1) 分経過した時点から i 分経過するまでの1分間に, 入口を通過した車の台数と出口を通過した車の台数が 1つの空白で区切られて書かれている.

調査開始後 j 分経過した時点 ( j=0, 1, 2, ... , n ) におけるトンネル内の車の台数を Sj とする. Sj の最大値を出力しなさい. また, トンネル内の車の台数が負になることは考えられないので, Sj が一度でも負になった場合は, 「エラー」の意味で 0 を出力しなさい. ただし, n は 10000 以下で, トンネルの入口および出口を1分間に通過する車の台数は 100 以下である.

 出力ファイルにおいては, 出力の最後の行にも改行コードを入れること.

入出力例

入力例1

3
2
2 3
2 3
4 1

出力例1

3

入力例2

3
2
2 3
2 4
4 1

出力例2

0

入力例3

3
2
2 3
2 3
1 0

出力例3

2

問題文と自動審判に使われるデータは、情報オリンピック日本委員会が作成し公開している問題文と採点用テストデータです。


Source: 5th Japanese Olympiad in Informatics, Trial Exam 2 , 2005-12-18
http://www.ioi-jp.org/