京都大学プログラミングコンテスト2013

F - 7歳教


Time limit時間制限 : 3sec / Memory limitメモリ制限 : 128MB

7歳の誕生日に"彼"は父から告げられた.

「お前が7歳になったということは,私はもう引退だ.今日からお前が7歳教の長だ.
7歳教の戒律により,7歳教の長が7歳の間だけ布教活動を行うことが認められている.
この宇宙船を使って,よりたくさんの人々に7歳教の素晴らしさを広めてきなさい.」

7歳教をよりたくさんの人に広めるために"彼"は,自分の周りの星についての情報を集めた.
"彼"の星の周りには,n 個の惑星があり,惑星は 1, ... , n で番号付けされていることがわかった.
惑星i から 惑星jの間を移動するには,w_i_j (年)の時間がかかることもわかった.

そして,それぞれの星で彼が7歳でいられる時間,つまり布教活動できる時間が異なることがわかった.
それぞれの惑星上では,宇宙暦l_i年1月1日00:00:00以降r_i年1月1日00:00:00より前までの時間帯であれば7歳でいられる.
たとえ一度ある星で7歳以外の年齢になっても,その星で後から7歳になった場合や,別の星で7歳になれば布教活動を再開することができる.

しかしどの星でどれくらい,そしてどの順序で布教活動を行えばより多くの人に7歳教を伝えることができるのか,
"彼"にはわからなかった.そこで"彼"はプログラミングが得意なあなたに助けを求めることにした.

現在は宇宙暦0年1月1日00:00:00であり,"彼"は惑星 s にいる. 惑星間を最適に移動・滞在した場合に布教活動が行える最長の年数,
つまり"彼"が7歳でかつ惑星で過ごす最長の年数Tを求めてあげよう. ただし,年数Tには移動時間は含まれない.

入力形式

入力は以下の形式で与えられる.

n s
l_1 r_1
     ...     
l_{n} r_{n}
w_{1,1}  w_{1,2} ... w_{1,n}
     ...     
w_{n,1} w_{n,2} ... w_{n,n}

n は惑星の個数である.s は主人公が最初にいる惑星をあらわす.
l_ir_i はそれぞれ,惑星i での7歳でいられる時間帯の下限と上限をあらわす.
w_i_j は,惑星iから惑星jを移動するのにかかる時間をあらわす.
入力はすべて整数である.

出力形式

答えTを出力せよ.

制約

  • 1 ≤ n ≤ 500
  • 1 ≤ s ≤ n
  • 0 ≤ l_i < r_i ≤ 10^8
  • 0 ≤ w_{ij} ≤ 10^8 (ij)
  • w_{ij} = 0 (i = j)

この問題の判定には,50 点分のテストケースのグループが設定されている.このグループに含まれるテストケースは上記の制約に加えて下記の制約も満たす.

  • すべての i, j に対して w_{ij} = 0

入出力例

入力例 1

2 1
0 100
150 250
0 100
100 0

出力例 1

150

入力例 2

5 1
7 44
10 49
38 48
11 23
11 30
0 1 7 2 7
10 0 3 8 10
4 8 0 2 5
3 2 1 0 4
8 4 3 3 0

出力例 2

41

Source name

京都大学プログラミングコンテスト2013

Submit提出する