No.654 Air E869120

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 256 MB / 通常問題
タグ : / 解いたユーザー数 50
作問者 : e869120e869120 / テスター : square1001square1001
2 ProblemId : 2027 / 出題時の順位表

問題文

"Air E869120" という航空会社は、毎日 $M$ 個の飛行機の便を yuki 国内で運行します。
yuki 国は 街 $1$, $2$, $3$, ..., $N$ の $N$ 個の街から成り、$i$ 個目の飛行機は、街 $u_i$ から $v_i$ まで飛び、時刻 $p_i$ に出発地を離陸し、時刻 $q_i$ に目的地に着陸します。また、この飛行機には $w_i$ 人乗ることができます。

2018/11/01 から、街 $1$ にある学校で 街 $N$ での修学旅行が行われる予定です。
偶然、2018/11/01 の飛行機は全部空席ですが、それ以降の予約できる飛行機は全部満席です。また、この学校の校長は "Air E869120" という航空会社以外信頼していないので、この航空会社の飛行機以外使うことは出来ません。

その時、最大で何人の生徒が修学旅行に行けるか、求めなさい。
ただし、生徒は時刻 $0$ に離陸する飛行機に乗ることは可能であり、一日の終わり (時刻 $10^9$) に街 $N$ の空港にいれば良いものとします。また、生徒は乗り継ぎに時間がかかるので、前の飛行機の着陸時刻と次の飛行機の離陸時刻の間に $d$ 分以上開ける必要があります。学校の生徒は十分に多いので、無限人いると仮定してもよいです。

入力

$N$ $M$ $d$
$u_1$ $v_1$ $p_1$ $q_1$ $w_1$
$u_2$ $v_2$ $p_2$ $q_2$ $w_2$
$u_3$ $v_3$ $p_3$ $q_3$ $w_3$
......
$u_M$ $v_M$ $p_M$ $q_M$ $w_M$

制約

  • $2 \le N \le 1000$
  • $1 \le M \le 1000$
  • $1 \le d \le 10^9$
  • $1 \le u_i, v_i \le N, u_i ≠ v_i$
  • $0 \le p_i < q_i \le 10^9$
  • $1 \le w_i \le 10^9$

出力

修学旅行で移動できる最大の人数を 1 行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 2 5
1 2 0 25 10
1 2 10 40 5
出力
15

飛行機 $1$ を使って $10$ 人、飛行機 $2$ を使って $5$ 人輸送できるので、合計で $10+5=15$ 人修学旅行に行くことができます。

サンプル2
入力
4 5 5
1 2 0 15 40
1 3 5 20 10
2 3 30 40 20
2 4 50 80 20
3 4 50 70 30
出力
50

$20$ 人が $1$->$2$->$4$ というルートをたどり、$20$ 人が $1$->$2$->$3$->$4$ というルートをたどり、$10$ 人が $1$->$3$->$4$ というルートをたどれば $50$ 人の輸送は可能です。

サンプル3
入力
3 4 5
1 2 0 10 10
1 2 10 20 3
2 3 15 25 2
2 3 5 15 10
出力
2

飛行機 $1$ -> 飛行機 $3$ というルート以外、乗り継ぎの関係上使うことができません。

サンプル4
入力
4 3 5
1 2 0 10 100
2 3 15 31 100
3 4 35 45 100
出力
0

残念ながら、この例では $1$ 分差で飛行機 $2$ から $3$ に乗り継ぐことができません。

サンプル5
入力
4 40 9
2 3 90 99 43
2 3 12 60 56
1 3 5 9 30
4 3 76 96 88
2 4 76 86 66
1 2 36 91 5
2 1 23 82 87
1 4 66 83 12
1 2 2 33 72
4 1 2 90 30
3 2 32 84 25
4 2 13 99 56
4 3 49 56 94
1 3 29 42 31
1 2 86 88 93
3 4 43 51 28
3 4 5 69 60
3 1 3 4 39
1 4 7 73 99
3 2 31 85 94
1 2 89 94 94
2 1 34 70 62
3 4 39 94 63
4 1 23 30 96
3 4 41 81 29
4 3 57 62 48
3 2 33 54 27
3 1 44 73 44
3 2 50 70 19
4 2 19 36 82
4 2 95 97 94
3 4 20 58 10
1 4 4 97 33
2 3 46 58 58
3 1 0 80 45
4 1 1 76 43
3 2 16 97 9
3 1 13 16 45
2 4 4 16 12
2 3 68 98 12
出力
240
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。