謝罪
全てにおいてガバガバで大変申し訳ございませんでした 以後気をつけます
問題
最近話題沸騰の音楽ゲーム『KOUNITHM』のランカーであるT君はなんと幻想入りしてしまった！
音ゲーうまい奴は人間じゃなくてゴリラだから当たり前だよね
妖怪に食われて死ぬとか嫌なのでさっさと紅魔館にでも避難しよう！
でもせっかく来たので途中で値打ちのあるマジックアイテムを拾っていきたい。
そこで、最短経路かつ安全で多くのアイテムを拾えるルートに導いてあげよう！
入力
h w m e x1 y1 c1 : xm ym cm x1 y1 : xe ye
1 行目にマップの縦幅 h 、マップの横幅 w 、アイテムの数 m 、妖怪の数 e が与えられる。
その後 m 行に渡りマジックアイテムの座標 x y 、 値打ち c が与えられる。
その後 e 行に渡り妖怪の座標 x y が与えられる。
妖怪のいる座標は通ることが出来ない。
出力
最短経路を通るときに拾えるアイテムの値打ちの最大を出力する。
制約
全ての入出力ケースについて以下を満たす。
- 1 ≦ h, w ≦ 50
- 0 ≦ m, e ≦ 200
- 0 ≦ c ≦ 143000
- 1 ≦ x, y ≦ 50
- ゴールには必ずたどり着くことが出来る。
- 現在地から上、左に進むことはない。
- また、座標情報は1から割り振られ,スタート地点は(1 , 1)、ゴール地点は(h , w)である。
入出力例
入力例
3 4 3 2 2 2 2 4 2 1 3 3 2 3 1 1 2
出力例
4
余談
CHUNITHMやってる新入生・先輩方いましたらei1718まで至急連絡くれや。
制服姿のまま音ゲーして、AIRだらけでやろうや。