#GYM104745M. The battle of Helm's Deep
The battle of Helm's Deep
本题没有可用的提交语言。
Description
There are $n$ towers at Helm's Deep, each of them has a power of $a_i$ and a strength of $b_i$. Rohan's strategists determine that the orcs will arrive in $q$ waves and that in the $j$-th wave $x_j$ orcs will attack tower $y_j$. In that wave, tower $y_j$ will take a damage of $max(0, x_j - a_{y_j} \cdot p_{y_j})$, where $p_{y_j}$ is the number of soldiers in tower $y_j$. Once any tower $i$ has taken an amount of damage that is at least $b_i$, it will be conquered. If some orcs attack an already conquered tower they will just go back to their lines confused (orcs aren't very intelligent). When a tower gets conquered, every soldier there will die. At the start of each wave (before the attack of that wave happens), the inner walls will get an amount of damage equal to the number of conquered towers at that moment. If the inner walls receive a lot of damage Rohan will fall and all hope for humans will be lost, so you want to minimize the damage received after the $q$ waves.
Rohan counts with $m$ soldiers and they ask you to help them locate the soldiers strategically. You must create the aforementioned array $p$ of length $n$, which must satisfy the following conditions:
- For all $i$, $0 \leq p_i \leq m$.
- $\sum p_i \le m$.
Let the minimum damage that the inner walls take over all possible arrays $p$ be $d$. You must determine the value of $d$ and the lexicographically smallest$^\dagger$ array $p$, so that the damage the inner walls take is exactly $d$.
$^\dagger$ An array $a$ is lexicographically smaller than a different array $b$ of the same length if, at the first position $i$ where they differ, $a_i < b_i$.
The first line of the input contains a single integer $t$, the number of test cases. ($1 \le t \le 100$).
The first line of each test case contains three integers $n$, $m$ and $q$, the number of towers, soldiers and waves, respectively. ($1 \le n \le 1000$; $0 \le m \le 1000$; $1 \le q \le 50000$).
Each of the following $n$ lines contains two integers, $a_i$ and $b_i$, the power and the strength of the $i$-th tower. ($1 \le a_i, b_i \le 10^9$).
Then come $q$ lines, each with two integers $x_j$ and $y_j$, the number of orcs and the tower they attack in the $j$-th wave, respectively. ($1 \le x_j \le 10^9$; $1 \le y_j \le n$).
It is guaranteed that neither the sum of $n$ nor the sum of $m$ will exceed $1000$ over all test cases, and that the sum of $q$ won't exceed $50000$ over all test cases.
For each test case, on the first line output $d$, the minimum damage the inner walls can take.
Then, output $n$ integers, the elements of the array $p$.
Input
The first line of the input contains a single integer $t$, the number of test cases. ($1 \le t \le 100$).
The first line of each test case contains three integers $n$, $m$ and $q$, the number of towers, soldiers and waves, respectively. ($1 \le n \le 1000$; $0 \le m \le 1000$; $1 \le q \le 50000$).
Each of the following $n$ lines contains two integers, $a_i$ and $b_i$, the power and the strength of the $i$-th tower. ($1 \le a_i, b_i \le 10^9$).
Then come $q$ lines, each with two integers $x_j$ and $y_j$, the number of orcs and the tower they attack in the $j$-th wave, respectively. ($1 \le x_j \le 10^9$; $1 \le y_j \le n$).
It is guaranteed that neither the sum of $n$ nor the sum of $m$ will exceed $1000$ over all test cases, and that the sum of $q$ won't exceed $50000$ over all test cases.
Output
For each test case, on the first line output $d$, the minimum damage the inner walls can take.
Then, output $n$ integers, the elements of the array $p$.
2
5 15 7
2 3
4 5
3 3
4 1
1 1
3 1
4 5
1 3
3 2
100 1
2 3
9 4
5 9 4
1 1
1 1
1 1
1 1
1 1
3 5
4 5
5 5
6 5
2
1 0 1 0 4
0
0 0 0 0 5
Note
—
Problem idea: Esomer
Problem preparation: Esomer
Ocurrences: Advanced 7