Optimal Land Division

In country \(Y\), there are \(N\) cities and \(M\) bidirectional roads connecting them such that any two cities are reachable from one another. After the king dies, his two sons, A and B, want to rule, but both wish to improve the stability of the nation without resorting to force. They decide to split the kingdom into two: country A and country B. City 1 is forcibly assigned to country A and city \(N\) is forcibly assigned to country B, while the remaining cities are free to be assigned to either side.

For each city \(i\), if it is assigned to country A it contributes a score \(VA_i\), and if assigned to country B, a score \(VB_i\). For every road \(e\) connecting cities \(u\) and \(v\), the following rules apply:

• If both \(u\) and \(v\) are in A, the road contributes \(EA_e\) points.
• If both are in B, it contributes \(EB_e\) points.
• If the road connects one city in A and the other in B, it loses its effectiveness and penalizes the score by \(EC_e\) points.

Your task is to determine an assignment of cities (with the restrictions that city 1 is in A and city \(N\) is in B) that maximizes the total score, which is computed as the sum of all city scores and all road scores.

The score for each road \(e\) connecting cities \(u\) and \(v\) can be written in LaTeX as follows:

[ S_e(x_u,x_v) = \begin{cases} EA_e, & \text{if } x_u = x_v = 0, \ EB_e, & \text{if } x_u = x_v = 1, \ -EC_e, & \text{otherwise.} \end{cases} ]

Here, we use the convention: 0 represents country A and 1 represents country B.

inputFormat

The first line contains two integers \(N\) and \(M\), representing the number of cities and roads respectively.

The next \(N\) lines each contain two integers \(VA_i\) and \(VB_i\) (for \(i=1,2,\dots,N\)), which are the scores for assigning city \(i\) to country A and country B respectively.

The following \(M\) lines each contain five integers \(u\), \(v\), \(EA_e\), \(EB_e\), \(EC_e\) representing a road connecting city \(u\) and city \(v\) with scores \(EA_e\) if both endpoints are in A, \(EB_e\) if both are in B, and a penalty \(EC_e\) if the endpoints are in different countries.

Note: City 1 is forced into country A and city \(N\) is forced into country B.

outputFormat

Output a single integer — the maximum total score achievable by optimally dividing the cities between the two countries.

sample

3 2
5 1
2 3
1 4
1 2 3 2 1
2 3 2 3 1

14