prithivMLmods/Coder-Stat

1 2 3<h1>Problem E: School Excursion</h1>4<p>5春、それは修学旅行の時期である。6会津大学附属小学校（会津大小）でも、来年度の修学旅行の計画が建てられていた。7修学旅行は電車で移動することが伝統になっている。8会津若松市内では電車を利用する機会が少ないためだ。9</p>10<p>11しかし、学校に届いたある苦情により教員たちは頭を悩ませていた。12それは、「ある駅で大人数で乗り換えを行っていたので、その駅を利用する他の乗客に迷惑であった」という内容だった。13とくに、電車を降りたあとホームからの通路で大混雑してしまったという。14</p>15<p>16それは近年、会津大小の生徒数が急上昇しているからであった。17その原因は日本において競技プログラミングが大流行し、18小学校から競技プログラマーを養成するための訓練を行っている会津大小に生徒が集まったからである。19</p>20<p>21会津大小競技プログラミング部長であるあなたは、修学旅行を楽しみにしている。22修学旅行を成功させたいあなたは教員たちに提案をした。23「クラスごとに行動して、同じ駅に同時に到着しないようにしましょう！！　競技プログラミングの知識を応用すれば簡単です！！」24</p>25<p>26複数のクラスが同時に同じ駅に到着することがないように移動するとき（同じ駅に複数のクラスが滞在することは可能）、27出発する駅から目的地まで到達できる最大のクラス数を求め、そのときの最小の運賃を求めるプログラムをつくりなさい。28ただし、ある駅で同時に到着する電車と発車する電車が存在する場合、乗り継ぎが可能である。つまり、乗り継ぎに要する時間は無視して良い。29</p>30 31<h2>Input</h2>32<p>33入力は複数のデータセットから構成される。34データセットの数は20個以下である。35各データセットの形式は次に示す通りである。36</p>37<pre>38n39m<sub>1</sub>40x<sub>1,1</sub> y<sub>1,1</sub> c<sub>1,1</sub>41x<sub>1,2</sub> y<sub>1,2</sub> c<sub>1,2</sub>42...43x<sub>1,m1</sub> y<sub>1,m1</sub> c<sub>1,m1</sub>44m<sub>2</sub>45x<sub>2,1</sub> y<sub>2,1</sub> c<sub>2,1</sub>46x<sub>2,2</sub> y<sub>2,2</sub> c<sub>2,2</sub>47...48x<sub>2,m2</sub> y<sub>2,m2</sub> c<sub>2,m2</sub>49...50m<sub>n-1</sub>51x<sub>n-1,1</sub> y<sub>n-1,1</sub> c<sub>n-1,1</sub>52x<sub>n-1,2</sub> y<sub>n-1,2</sub> c<sub>n-1,2</sub>53...54x<sub>n-1,m2</sub> y<sub>n-1,m2</sub> c<sub>n-1,m2</sub>55g56</pre>57<p>58n( 2 &le; n &le; 100)は駅の数を表す。59駅の数は出発する駅と目的地の駅、乗り換えする駅を含む。60駅は出発する駅を1番目、最初に乗り換える駅を2番目の駅と数え、目的地をn番目の駅とする。61m<sub>i</sub>はi番目の駅からi+1番目の駅への電車の数を表す。62m<sub>i</sub>(1 &le; m &le; 20)個の電車の情報が続く。63x<sub>i,j</sub> y<sub>i,j</sub> c<sub>i,j</sub>64はi番目の駅からi+1番目の駅に向かう電車の出発時刻(x<sub>i,j</sub>)到着時刻(y<sub>i,j</sub>)運賃(c<sub>i,j</sub>)を表す。65(0 &le; x<sub>i,j</sub>, y<sub>i,j</sub> &le; 200000 かつ x<sub>i,j</sub> &le; y<sub>i,j</sub>)66(1 &le; c<sub>i,j</sub> &le; 1000)67 68その後g(1&le; g &le; 10)が続く。69gは修学旅行に参加するクラス数を表す。70与えられる数（n,m,x,y,c,g)はすべて整数である。71入力の終了はひとつの0を含む１行で示される。72</p>73<h2>Output</h2>74<p>75一行に到着可能なクラス数とそのときの最小運賃をこの順に出力せよ。76もし、ただ一つのクラスも到着できない場合は0 0を出力せよ。77</p>78 79<h2>Sample Input</h2>80<pre>812824831 2 10842 2 5851 3 20862 3 108710883892901 2 5910 3 49239310 11 100942 12 29512 12 3961097098</pre>99 100<h2>Sample Output</h2>101<pre>1022 151032 111104</pre>