You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

鸡尾酒是一个多操手，他可以同时操作 𝑚个账号。今天，他使用这些账号一起 打一个boss。

这个 boss 战的地图共有 𝑛 个关键点，其中有 𝑛 − 1 条边，每 条边连接着两个不同的点，使得从任意点出发可以到达其他所有的点。

鸡尾酒的 𝑚 个账号分别编号 1 至 𝑚 ，一开始，第 𝑖 个账号在点 $𝑠_𝑖$。可能有两个账号在同一位置。

现在，boss 放出了一个致命技能。boss在地图上标出了 𝑚 个关键点，想成功 躲避这个技能，必须在每一个被标记的点上，都有一个账号站在上面。注意，可能会有点被多次标记，多次标记的点需要有多个账号站在上面。 由于鸡尾酒无法分身，所以他必须先把一个账号移动到一个位置，才能动另一个 账号，不能同时移动多个账号。假设鸡尾酒的任意账号通过第 𝑖 条边的时间为 $𝑤_𝑖$，请帮鸡尾酒求出他成功躲避技能所需要的最少时间。

输入格式

一行两个正整数 𝑛 和 𝑚 ，分别表示关键点的数量和标记点的数量。 后面一行 𝑚个数字 $𝑠_1, 𝑠_2 , … , 𝑠_𝑚$ , $𝑠_𝑖$ 表示第 𝑖 个账号的初始位置。 再后面一行 𝑚 个数字，表示标记点的位置。 后面 𝑛 − 1 行每行三个数字 $𝑢_𝑖, 𝑣_𝑖, 𝑤_𝑖$，表示有一条连接 $𝑢_𝑖, 𝑣_𝑖$ 的边，经过时间为 $𝑤_𝑖$。 由于𝑏oss想要为难鸡尾酒，所以所有的 $𝑤_𝑖$ 都是反着给出的，即低位在前，高位

输出格式

一行一个正整数，表示最少时间。

6 4
5 1 3 2
4 2 1 2
1 2 5
2 3 6
2 4 7
1 5 4
1 6 4

22

10 3
2 3 4
1 8 10
1 2 5
1 3 6
1 4 7
3 5 11
4 6 11
5 9 43
6 7 34
9 10 13
7 8 42

159

2 10
1 1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2 2
1 2 1234567891001987654321

12345678910019876543210

提示与说明

请使用较快的输入方式。 本题共 25 个数据点，每个测试点等分(即一个测试点 4 分)。 保证对于所有数据，1 ⩽ 𝑛, 𝑚 ⩽ $10^5$, 1 ⩽ $𝑤_𝑖$ ⩽ $10^{100}$。 保证对于 20% 的数据，1 ⩽ 𝑛, 𝑚 ⩽ 10,1 ⩽ $𝑤_𝑖$ ⩽ $10^5$。 保证对于另外 20% 的数据，1 ⩽ 𝑚 ⩽ 10,1 ⩽ $𝑤_𝑖$ ⩽ $10^5$。 保证对于另外 40% 的数据，1 ⩽ $𝑤_𝑖$ ⩽ $10^5$ 。