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
If this questions let you collect items not in order, it will be a 12 or 15 points question