← 返回题目列表

AtCoder · maximum_2013_f

F. 三骑士和一条狗

中文机器翻译题面 查看原题

問題

“我必须为主做任何事。” 他们是侍奉领主的骑士(这里有3个人1条狗,1条狗就叫狗)。 为了治愈主人的病,他们打败了拥有强大魔力的人,并从拥有者那里窃取了魔力。 这是因为他们相信,如果他们播撒魔法力量,就可以治愈他们的主人。 就在前几天,我从两个巫师那里得到了魔力。 看起来魔法聚会进行得很顺利,但主人的病情却比预想的发展得更快。 另外,由于不可能多次从同一个魔力持有者那里获取魔力,所以你还必须考虑到寻找人来收集它需要花费的时间和精力。 为此,到现在为止我一直是几个人的团队一起工作,但从现在起我别无选择,只能单独行动。 你应该为以后的战斗保存体力,当然,移动也会消耗体力(称为移动力),所以你要尽可能减少移动。

你的任务是求出当骑士和魔力持有者的位置和魔力数量给定时,以及通过收集最多一名骑士的魔力来收集最大魔力时所需的最低移动力。

移动力量与曼哈顿距离成正比。例如,如果骑士的坐标是(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 有保证。
  3. 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