幸福国度可以用 个城镇（用 到 编号）构成的集合来描述，这些城镇最开始由 条双向道路（用 到 编号）连接。城镇 是中央城镇。保证一个人从城镇 出发，经过这些道路，可以到达其他的任何一个城市。这些道路都是收费道路，道路 的使用者必须向道路的主人支付 分钱的费用。已知所有的这些 是互不相等的。最近有 条新道路建成，这些道路都属于亿万富豪 Mr. Greedy。
Mr. Greedy 可以决定每条新道路的费用（费用可以相同），并且他必须在明天宣布这些费用。
两周以后，幸福国度将举办一个盛况空前的嘉年华！大量的参与者将沿着这些道路游行并前往中央城镇。共计 个参与者将从城镇 出发前往中央城镇。这些人只会沿着一个选出的道路集合前行，并且这些选出的道路将在这件事的前一天公布。根据一个古老的习俗，这些道路将由幸福国度中最有钱的人选出，也就是 Mr. Greedy。同样根据这个习俗，Mr. Greedy 选出的这个道路集合必须使所有选出道路的费用之和最小，并且仍要保证任何人可以从城镇 前往城镇 （因此，这些选出的道路来自将费用作为相应边边权的 “最小生成树”）。如果有多个这样的道路集合，Mr. Greedy 可以选其中的任何一个，只要满足费用和是最小的。
Mr. Greedy 很明确地知道，他从 条新道路中获得的收入不只是与费用有关。一条道路的收入等于所有经过这条路的人的花费之和。更准确地讲，如果 个人经过道路 ，道路 产生的收入为乘积 。注意 Mr. Greedy 只能从新道路收取费用，因为原来的道路都不属于他。
Mr. Greedy 有一个阴谋。他计划通过操纵费用和道路的选择来最大化他的收入。他希望指定每条新道路的费用（将在明天公布），并且选择嘉年华用的道路（将在嘉年华的前一天公布），使得他在 条新道路的收入最大。注意 Mr. Greedy 仍然需要遵循选出花费之和最小的道路集合的习俗。
你是一个记者，你想揭露他的计划。为了做成这件事，你必须先写一个程序来确定 Mr. Greedy 可以通过他的阴谋获取多少收入。
输入格式
第一行包含三个由空格隔开的正整数 和 。
接下来的 行描述最开始的 条道路。这 行中的第 行包含由空格隔开的整数 ，表示有一条在 和 之间，费用为 的双向道路。保证 。保证如果 ，则 。
接下来的 行描述新建的 条道路。这 行中的第 行包含由空格隔开的整数 和 ，表示有一条连接城镇 和 新道路。保证 。
最后一行包含 个由空格隔开的整数，其中的第 个为 ，表示从城镇 前往城镇 的人数。
保证在任意两个城市之间，最多只有一条道路（包括新建的道路）。
输出格式
你的程序必须输出恰好一个整数到标准输出，表示能获得的最大的收入。
样例一
input
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
output
400
explanation
Mr. Greedy 应该将新道路 的费用设置为 分钱。在这个费用下，他可以选择道路 和 来最小化总费用，这个费用为 。
从城镇 出发的 个人和从城镇 出发的 个人将经过新道路前往城镇 ，因此他可以获得为 分钱的最好收入。
如果我们这样做，将新道路 的费用设置为 分钱。根据传统的限制，Mr. Greedy 必须选择 和 ，因为这是唯一费用最小的集合。
因此，在嘉年华的过程中道路 将没有任何收入。
限制与约定
我们将使用以下 5 类测例测试你的程序。
对每个 和 ，。
- （ 分） 且 ;
- （ 分） 且 ;
- （ 分） 且 ;
- （ 分） 且 ;
- （ 分） 且 。
时间限制：
空间限制：
下载
样例数据下载
鄂公网安备 42010202000505 号