Description

Country Y has $N$ cities and $M$ bidirectional roads connecting them, and any two cities are connected by at least one path. After the death of the king of Country Y, his two sons A and B both wish to become the new king, but they both want greater stability and will not use force. They decide to divide the country into two smaller countries: Country A and Country B. Currently, A owns city $1$, and B owns city $N$. The ownership of the other cities has not yet been determined (after the division, the cities within the same country do not need to be connected).

Since everyone wants the country to prosper, some cities prefer the king’s son A as their leader, while others favor B. For transportation convenience, if a road connects two cities within the same country after the division, it is more beneficial for intercity communication. Therefore, the ministers designed a scoring mechanism for the land division, as follows:

For city $i$, if it is assigned to Country A, it yields a score of $\mathit{VA}_i$; if it is assigned to Country B, it yields a score of $\mathit{VB}_i$. For a road $i$, if it connects two cities in Country A, it yields a score of $\mathit{EA}_i$; if it connects two cities in Country B, it yields a score of $\mathit{EB}_i$; otherwise, the road becomes useless and incurs a penalty of $\mathit{EC}_i$.

Please find the optimal land division that maximizes the total score.

Input Format

The first line contains two integers $N$, $M$, as described above.
The next line contains $N - 2$ non-negative integers, representing $\mathit{VA}_2,\mathit{VA}_3,\cdots,\mathit{VA}_{N-1}$.
The next line contains $N - 2$ non-negative integers, representing $\mathit{VB}_2,\mathit{VB}_3,\cdots,\mathit{VB}_{N-1}$.
The next $M$ lines each contain five non-negative integers describing a road: $X, Y, \mathit{EA}_i, \mathit{EB}_i, \mathit{EC}_i$, with meanings as described above.

Output Format

Output exactly one integer, the maximum score.

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

11

Hint

Constraints: $N \le 10^4$, $M \le 4 \times 10^4$.

It is guaranteed that all intermediate values and the final result fit within the range of a 32-bit signed integer.

Translated by ChatGPT 5