F - 3人の騎士と1匹の犬
Editorial
/ 
入力は以下の形式で標準入力から与えられる。
必要となる移動力の最小値を 1 行で出力すること。 また、出力の最後には改行をいれること。
/ 
Time Limit: 2 sec / Memory Limit: 256 MB
問題
「主のために何としてもやり遂げねば」。 彼らは主に仕える騎士（ここにいるのは3人と1匹。1匹は犬と呼ばれている）である。 彼らは主の病を治すため、強力な魔力の保有者を打ち倒し、魔力保有者から魔力を奪い蒐めている。 魔力が蒐まれば主を治癒できると信じているからである。 つい先日も2人の魔法使いから魔力を蒐めたばかりである。 魔力蒐集も順調かと思われていたが、主の病の進行が思いの外、速い。 加えて、同じ魔力保有者から複数回魔力を奪うことはできない為、蒐集対象を探す手間も考えなければならない。 このため、今までは数人でチームを組み、事にあたってきたがこれからは単独で行動するより他にない。 今後の戦闘のために、体力は温存しておくべきで、当然、移動にも体力(移動力と呼ぶ)を消費するので出来るだけ移動を減らしたい。
あなたの仕事は、騎士達や魔力保有者達の 位置や魔力量が与えられた時、 騎士一人高々一体の魔力蒐集を行って最大量の魔力を蒐めた時、 必要となる移動力の最小値を求めることである。
移動力はマンハッタン距離に比例します。 例えば、騎士の座標が(1,1)で、魔力保有者の座標が(2,3)である場合、その間の移動には 3 移動力必要となります。 また、この世界に同一の名前を持つ人物は複数人存在しないものとします。
入力
N M KNIGHT\_NAME_1 KX_1 KY_1 : KNIGHT\_NAME_N KX_N KY_N MAGE\_NAME_1 MAGIC_1 MX_1 MY_1 : MAGE\_NAME_M MAGIC_M MX_M MY_M
- 1行目には整数 N, M が与えられます。
- N は騎士の数を表します。
- M は魔力保有者の数を表します。
- 1 ≦ N, M ≦ 50 であることは保証されています。
- 2行目から N+1 行目までの N 行では、騎士の名前、X座標およびY座標がそれぞれ半角スペース区切りで与えられます。
- KNIGHT\_NAME_i は i 番目の騎士の名前を表します。
- KX_i は i 番目の騎士のX座標を表します。
- KY_i は i 番目の騎士のY座標を表します。
- KNIGHT\_NAME_i は半角英数字1文字以上20文字以下であることが保証されています。
- 0 ≦ KX_i, KY_i ≦ 10,000 であることは保証されています。
- N+2 行目から N+M+1 行目までの M 行では、魔力保有者の名前、魔力量、X座標およびY座標がそれぞれ半角スペース区切りで与えられます。
- MAGE\_NAME_i はi番目の魔力保有者の名前を表します。
- MAGIC_i はi番目の魔力保有者の魔力量を表します。
- MX_i はi番目の魔力保有者のX座標を表します。
- MY_i はi番目の魔力保有者のY座標を表します。
- MAGE\_NAME_i は半角英数字1文字以上20文字以下であることが保証されています。
- 0 ≦ MAGIC_i ≦ 10,000,000 および 0 ≦ MX_i, MY_i ≦ 10,000 であることは保証されています。
出力
入力例
4 4 Sigunum 3 2 Viita 2 2 Shamall 3 3 Zafiira 2 3 Kame 10 1 1 Tora 10 4 1 Hebi 10 1 4 Niwatori 10 4 4
出力例
8