I. Itinerary of a Tourist
time limit per test
4.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Thiago is a tourist exploring the wonderful city of Curitiba, in Paraná, famous for its beauty (and cold weather). The map of the region can be represented by $$$N$$$ locations and $$$M$$$ roads connecting them. Each road has an associated travel time, in minutes.

Thiago wants to visit $$$P$$$ tourist attractions, which are the first $$$P$$$ locations on his map, such as the Botanical Garden, the Oscar Niemeyer Museum, and the huge UFPR. For each of these attractions, he has assigned a value of "happiness" that he would feel when visiting them for the first time.

Unfortunately, his time is short. He has only one day for his tour, which starts at 8:00 a.m. at his hotel (located at location $$$N$$$) and must end before midnight (12:00 a.m.). The time to visit each location depends on the tourist attraction to be visited. He can visit the tourist attractions in any order he wants and does not need to return to the hotel.

As a close friend of Thiago's and a skilled programmer, you have decided to assist him. Your task is to develop a program that determines the optimal route for Thiago, that is, the maximum sum of happiness from the locations visited without exceeding the time limit.

Input

The first line of the input contains four integers: the number of locations $$$N$$$ ($$$2 \le N \le 2 \times 10^{5}$$$), the number of roads $$$M$$$ ($$$N-1 \le M \le 2 \times 10^{5}$$$), and the number of tourist attractions $$$P$$$ ($$$1 \le P \le 20$$$). It is guaranteed that the graph is connected and that $$$P \lt N$$$.

The next $$$M$$$ lines describe the roads in the city. Each line contains three integers $$$u$$$, $$$v$$$, and $$$w$$$, where $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le N$$$) represent the locations connected by the road, and $$$w$$$ ($$$1 \le w \le 180$$$) represents the travel time in minutes. The roads are two-way, and there are no repeated roads or roads with $$$u = v$$$ in the input.

The next line contains $$$P$$$ distinct integers $$$f_1, f_2,\ldots,f_P$$$ where each $$$f_i$$$ ($$$1 \le f_i \le 10^5$$$) represents the happiness Thiago gets from visiting tourist spot $$$i$$$ for the first time.

The last line of the input contains $$$P$$$ integers $$$t_1, t_2,\ldots,t_p$$$ where $$$t_i$$$ ($$$1 \le t_i \le 120$$$) represents the time spent, in minutes, at tourist attraction $$$i$$$.

Output

Output a single integer, the maximum amount of happiness that Thiago can achieve.

Examples
Input
4 3 2
4 1 100
1 3 150
3 2 50
50 80
30 40
Output
130
Input
8 10 4
8 6 120
6 1 150
1 2 100
2 3 170
3 4 180
4 7 90
7 5 110
6 4 160
1 7 170
8 5 130
100 60 70 80
120 60 80 40
Output
250
Input
5 4 3
5 4 170
5 1 170
4 2 170
2 3 100
160 120 110
120 120 120
Output
280