Problem Statement

There are \(N\) towns, numbered \(1 \ldots N\).
Some of the towns are directly connected by roads, and others are not.
Each road goes from town \(S_i\) to town \(T_i\), costs \(Y_i\) yen to travel, and takes \(M_i\) units of time.

You are in town \(1\).
You want to go to town \(N\).
You may pass through any number of roads and towns, but you currently have only \(C\) yen.

(That is, the total of the costs \(Yi\) of the roads you use must be at most \(C\).)

Among these options, when you choose the route that arrives earliest, answer its total units of time.
If you cannot reach the destination under this constraint, return \(-1\).

Input

\(N\)
\(C\)
\(V\)
\(S_1\ S_2\ S_3\ \dots\ S_V\)
\(T_1\ T_2\ T_3\ \dots\ T_V\)
\(Y_1\ Y_2\ Y_3\ \dots\ Y_V\)
\(M_1\ M_2\ M_3\ \dots\ M_V\)

The \(1\)st line contains an integer \( N\ ( 2 \leq N \leq 50 ) \), the number of towns.
The \(2\)nd line contains an integer \( C\ ( 1 \leq C \leq 300 ) \), the amount of money you have.
The \(3\)rd line contains an integer \( V\ ( 1 \leq V \leq 1500 ) \), the number of roads.
The \(4\)th line contains \(V\) space-separated values \(S_i\ ( 1 \leq S_i \leq N ) \).
The \(5\)th line contains \(V\) space-separated values \(T_i\ ( S_i \lt T_i \leq N ) \).
The \(6\)th line contains \(V\) space-separated values \(Y_i\ ( 1 \leq Y_i \leq 300 ) \).
The \(7\)th line contains \(V\) space-separated values \(M_i\ ( 1 \leq M_i \leq 1000 ) \).

\(S_i, T_i, Y_i, M_i\) mean that, for each index \(i\), traveling from town \(S_i\) \(\rightarrow\) town \(T_i\) (a directed graph) costs \(Y_i\) and takes \(M_i\) units of time.

The graph formed by connecting the towns with roads has no cycles (loops), and in terms of numbering, \(S_i \lt T_i\) holds.
That is, you do not need to consider routes that go back in numbering (for example, from town \(3\) to town \(1\)).
Depending on how the roads are connected, it may be impossible to reach town \(N\).
There may be multiple routes for \(S_i \rightarrow T_i\).

Output

When you choose the route from town \(1\) to town \(N\) that arrives earliest, answer its total units of time.
If you cannot reach the destination under this constraint, return -1.
Print a newline at the end.

Sample

3
100
3
1 2 1
2 3 3
10 90 10
10 10 50

20

3
100
3
1 2 1
2 3 3
1 100 10
10 10 50

50

10
10
19
1 1 2 4 5 1 3 4 6 4 6 4 5 7 8 2 3 4 9
3 5 5 5 6 7 7 7 7 8 8 9 9 9 9 10 10 10 10
8 6 8 7 6 6 9 9 7 6 9 7 7 8 7 6 6 8 6
8 9 10 4 10 3 5 9 3 4 1 8 3 1 3 6 6 10 4

-1

2
1
2
1 1
2 2
1 2
100 10

100