1917. 神奇宝贝大师

【题目描述】

“我的梦想是成为神奇宝贝大师！”小智说。

广告时间:duang!

神奇宝贝新女主角：Serena

10岁的小智在观众老了15岁之后仍然10岁,战斗不靠实力靠激情、不上课、到哪儿都有大酒店住，还不花钱，这就是科学的神奇宝贝世界。

为了更快的成为神奇宝贝大师，小智按时参加每个地区的全国奥林匹克神奇宝贝竞赛

（National Olympic Pokemon Competition,简称NOPC）,并期望能获得国家一等奖，这样小智不仅能进入国家集训队，争取资格参加世界奥林匹克神奇宝贝竞赛(International Olympic Pokemon Competition,简称IOPC),还能被保送到关都地区最好的大学—神奇宝贝清华大学。

小智还前往杭州学军神奇宝贝俱乐部，参加了去年的全国奥林匹克神奇宝贝冬令营（National Olympic Pokemon Winter Camp,简称NOPWC），并打败了几乎所有国家集训队成员，获得了第二名，只败给了银策同学.在冬令营的快乐生活中，他被一个妹子萌出了一脸血并顺利的泡到了20分妹子瑟蕾娜。唯一让小智遗憾的是，他在去年的NOPC中策略失误，导致没有拿到金牌

---------------------------

  以上内容仅供娱乐，与本题毫无关联

卡洛斯大陆有许多个地区，每个地区有一定数量的训练师，假设小智是神，能击败该地区所有训练家，获得该地区所有训练家所携带的经验值，但是小智的路费有限，小智从一个地区坐飞机到另一个地区需要花钱。

但是每次飞往一个地区，击败该地区的训练家后，神奇宝贝奥委会就会免费（强制）送小智回老家看望妈妈。小智途径某地区（不是单次旅行的终点）时，不能挑战该地的训练家。为了帮小智获得更多的经验值，请你帮忙。同时，小智的爸爸要去许多地区旅行，小智需要帮爸爸计算从一个地区到另一个地区所花的最小路费。

我们用某地区训练家的集合来表示这个地区，

请先看提示。

【输入格式】

第一行一个整数：n

表示有n位训练家。

第二行到第n+1行：每行一个字符串name[i],经验值exp[i]。

第n+2行：一个整数m

表示有m个提示。

第n+3行到n+m+3行，每行两个字符串name1,name2,表示两个训练家在同一个地区(如果训练家没有被提示，则他单独在一个地区)

第n+m+4行是一个整数k

表示道路数。

第n+m+5行到n+m+k+5行:每行两个字符串name3,name4,value,表示两个训练师所在地区相互之间的路费。(保证两个训练师不在同一个地区)

（可能有相同的路，以后读入的为准）

第n+m+k+6行：一个字符串name5，表示小智和某个训练师在同一个地区，且该地区是小智的老家。

第n+m+k+7行：一个自然数money,表示小智的钱。

第n+m+k+8行：一个整数q,表示q个询问

第n+m+k+9到n+m+k+q+9行：每行两个字符串name6,name7，表示询问两个训练家所在地区互相到达的最小路费

【输出格式】

第一行一个整数EXPmax，因为EXPmax可能很大，请输出EXPmax对10000007取模的结果，如果小智无法获得任何经验，输出0。

第2到第2+q行

对q个询问的回答，如果两地没有道路，输出-1.

【样例输入】

7

A 1

B 2

C 3

D 4

E 5

F 6

G 7

3

A B

B D

C E

3

A C 3

B G 2

C G 4

G

5

1

D E

【样例输出】

15

1

【提示】

训练家ABD在同一个地区a,CE在一个地区b，小智与G在同一个地区,设小智的老家是c(G)

则地区a经验值1+2+4为7，b经验值3+5为8，value[a][b]=1,value[a][c]=2,value[b][c]=4;

小智可以先从c地区飞向a地区，返回老家c地区，再从c地区飞向a地区，再从a地区飞向b地区，获得a,b地区的经验值总共=7+8=15.且小智的路费为5全部耗光（1+2+2）。

D,E所在地区a,b最小路费为1

样例说明

注意事项：1.小智不会挑战他老家的训练师。

2.如果地区A到B路费20元，B到C路费30元，A到C路费100元，则小智可以选择从A飞到B，再从B飞到C，以此类推，为了省路费，小智可以多次转机，但是，小智途径某地，无法挑战该地的训练家。

3.小智有强迫症，无法重复挑战某地的训练家。

数据范围

N<=150

M<=N-1

地区数<=150

Value<=10000

q<=10000

小智的钱数<=10000001

【来源】

任地狱友情出品，感谢mikumikumi的友情赞助（帮忙做测试数据）。