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_i と r_i はそれぞれ,惑星i での7歳でいられる時間帯の下限と上限をあらわす.
w_i_j は,惑星iから惑星jを移動するのにかかる時間をあらわす.
入力はすべて整数である.
答えTを出力せよ.
2 1 0 100 150 250 0 100 100 0
150
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
41