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

#### Constraints

Building will never contain any items.

##### Subtask 1 [4/15]

A building will contain at most item.

##### Subtask 2 [4/15]

##### Subtask 3 [7/15]

No additional constraints.

#### Input Specification

The first line contains integers, , , and , the number of buildings, the number of roads, and the number of items you need to collect, respectively.

The next line contains space separated integers, , where is the time it takes to build item yourself.

The next line contains space separated integers, , where is the number of buildings that contain item .

The of the next lines contain space separated integers, the buildings that contain item .

The next lines contain space separated integers, , , and , representing a two-way road between buildings and , taking minutes to travel.

#### Output Specification

Output one integer, the minimum time it takes to obtain all 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 .

The optimal way to obtain all items is:

- Create item yourself.
- Go from building to building .
- Go from building to building . Collect item here.
- Go from building to building . Collect item here.

In total, you take 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 .

The optimal way to obtain all items is:

- Go from building to building .
- Go from building to building . Collect item here.
- Go from building to building .
- Go from building to building . Collect item here.

In total, you take 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 to building . Collect item and here.
- Create item yourself.

In total, you take minutes, which is the minimum time possible.

## Comments