Description

In a basketball league, there are $n$ teams. A team's expenditure is related to its numbers of wins and losses. Specifically, the season's total expenditure of the $i$-th team is $C_i\times x^2+D_i \times y^2,D_i \le C_i$. (The more you win, the more bonuses you pay to the players.)

Now the season is halfway through. Each team has achieved $a_i$ wins and $b_i$ losses. There are still $m$ games to be played. Find the minimum total expenditure across all teams in the league.

Input Format

The first line contains $n$ and $m$.

Each of the next $n$ lines contains $4$ integers $a_i,b_i,C_i,D_i$.

Each of the next $m$ lines contains two integers $s$, $t$, meaning the $s$-th team and the $t$-th team will play one game. Note that there may be multiple games between the same pair of teams.

Output Format

Print one integer representing the minimum total expenditure.

3 3
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1

43

Hint

For $20\%$ of the testdata, $2 \le n \le 10,0 \le m \le 20$.

For $100\%$ of the testdata, $2 \le n \le 5000,0 \le m \le 1000,0 \le D_i \le C_i \le 10,0 \le a_i,b_i \le 50$.

Translated by ChatGPT 5