Xiao C has a directed graph with $n$ vertices and $m$ edges, where the vertices are numbered $1, 2, \dots, n$, and the $i$-th edge is $u_i \to v_i$.

Xiao C wants to modify this directed graph such that the resulting new graph contains no cycles.

For the $i$-th edge, Xiao C can pay a cost of $a_i$ to reverse it (i.e., change it to $v_i \to u_i$), or pay a cost of $b_i$ to delete it.

For the $i$-th vertex, Xiao C can pay a cost of $c_i$ to delete it along with all edges connected to it.

Please write a program to find the modification plan with the minimum total cost.

Input

The first line contains two positive integers $n, m$ ($2 \le n \le 22$, $1 \le m \le n(n - 1)$), representing the number of vertices and edges, respectively.

The second line contains $n$ positive integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^6$), representing the cost to delete each vertex.

The next $m$ lines each contain four positive integers $u_i, v_i, a_i, b_i$ ($1 \le u_i, v_i \le n$, $u_i \neq v_i$, $1 \le a_i, b_i \le 10^6$), describing each edge.

The input data guarantees that there is at most one edge of each orientation between any pair of vertices.

Output

Output a single integer, which is the minimum total cost.

Examples

Input 1

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

Output 1

4

Input 2

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

Output 2

3

Input 3

3 1
1 1 1
1 2 3 4

Output 3

0