P4307 [JSOI2009] Team Revenue / Team Budget

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.

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.

Print one integer representing the minimum total expenditure.

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