You are participating in a scavenger hunt in a city with ~N~ buildings (~1~-indexed) and ~M~ two-way roads connecting buildings ~a_i~ and ~b_i~, taking ~c_i~ minutes to travel. You are currently in building ~1~ and your goal is to obtain ~K~ items labelled from ~1~ to ~K~ which are scattered across the city, in order. The ~i^{th}~ item will be present in ~k_i~ buildings. Building ~1~ is guaranteed to never contain any items and a building may contain more than ~1~ item. For each item, you also have the option to stand still and create it yourself in ~m_i~ minutes. What is the minimum amount of time you need to obtain all ~K~ items?

Constraints

~1 \le N, M \le 20\,000~

~1 \le a_i, b_i \le N~

~a_i \neq b_i~

~1 \le c_i \le 10^6~

~1 \le m_i \le 10^9~

~1 \le K \le 30~

~1 \le k_i < N~

Building ~1~ will never contain any items.

Subtask 1 [4/15]

~k_i = 1~

A building will contain at most ~1~ item.

Subtask 2 [4/15]

~m_i = 10^9~

~c_i \le 10^3~

Subtask 3 [7/15]

No additional constraints.

Input Specification

The first line contains ~3~ integers, ~N~, ~M~, and ~K~, the number of buildings, the number of roads, and the number of items you need to collect, respectively.

The next line contains ~K~ space separated integers, ~m_1, \dots, m_K~, where ~m_i~ is the time it takes to build item ~i~ yourself.

The next line contains ~K~ space separated integers, ~k_1, \dots, k_K~, where ~k_i~ is the number of buildings that contain item ~i~.

The ~i^{th}~ of the next ~K~ lines contain ~k_i~ space separated integers, the buildings that contain item ~i~.

The next ~M~ lines contain ~3~ space separated integers, ~a_i~, ~b_i~, and ~c_i~, representing a two-way road between buildings ~a_i~ and ~b_i~, taking ~c_i~ minutes to travel.

Output Specification

Output one integer, the minimum time it takes to obtain all ~K~ items in minutes.

Sample Input 1

4 4 3
9 10 10
1 1 1
3
4
2
1 2 3
2 3 5
2 4 4
3 4 10

Sample Output 1

20

Explanation for Sample Output 1

This sample case satisfies the condition of subtask ~1~.

The optimal way to obtain all items is:

• Create item ~1~ yourself.
• Go from building ~1~ to building ~2~.
• Go from building ~2~ to building ~4~. Collect item ~2~ here.
• Go from building ~4~ to building ~2~. Collect item ~3~ here.

In total, you take ~9 + (3 + 4 + 4) = 20~ minutes, which is the minimum time possible.

Sample Input 2

5 6 2
1000000000 1000000000
1 2
3
4 5
1 2 1
1 3 4
2 3 2
2 4 1
3 5 6
5 4 2

Sample Output 2

6

Explanation for Sample Output 2

This sample case satisfies the condition of subtask ~2~.

The optimal way to obtain all items is:

• Go from building ~1~ to building ~2~.
• Go from building ~2~ to building ~3~. Collect item ~1~ here.
• Go from building ~3~ to building ~2~.
• Go from building ~2~ to building ~4~. Collect item ~2~ here.

In total, you take ~1 + 2 + 2 + 1 = 6~ minutes, which is the minimum time possible.

Sample Input 3

4 6 3
3 3 5
2 3 1
2 3
2 3 4
3
1 2 4
1 3 10
2 3 6
1 4 2
2 4 3
3 4 8

Sample Output 3

9

Explanation for Sample Output 3

The optimal way to obtain all items is:

• Go from building ~1~ to building ~2~. Collect item ~1~ and ~2~ here.
• Create item ~3~ yourself.

In total, you take ~4 + 5 = 9~ minutes, which is the minimum time possible.