5353: New Equipments II
内存限制：512 MB
时间限制：7.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Little Q's factory recently purchased n pieces of new equipment, labeled by 1,2,…,n.
There are n workers in the factory, labeled by 1,2,…,n. Each worker can be assigned to no more than one piece of equipment, and no piece of equipment can be assigned to multiple workers. If Little Q assigns the i-th worker to the j-th piece of equipment, they will bring ai+bj profits. However, these workers are not so experienced, there are m extra constraints. In each constraint, you will be given two integers ui and vi, denoting the ui-th worker can't be assigned to the vi-th piece of equipment.
Now please for every k (1≤k≤n) find k pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total profits for these k pairs are maximized, or determine it is impossible.
There are n workers in the factory, labeled by 1,2,…,n. Each worker can be assigned to no more than one piece of equipment, and no piece of equipment can be assigned to multiple workers. If Little Q assigns the i-th worker to the j-th piece of equipment, they will bring ai+bj profits. However, these workers are not so experienced, there are m extra constraints. In each constraint, you will be given two integers ui and vi, denoting the ui-th worker can't be assigned to the vi-th piece of equipment.
Now please for every k (1≤k≤n) find k pairs of workers and pieces of equipment, then assign workers to these pieces of equipment, such that the total profits for these k pairs are maximized, or determine it is impossible.
输入
The first line contains a single integer T (1≤T≤200), the number of test cases. For each test case:
The first line contains two integers n and m (1≤n≤4000, 1≤m≤10000), denoting the number of workers/pieces of new equipment and the number of constraints.
The second line contains n integers a1,a2,…,an (1≤ai≤109).
The third line contains n integers b1,b2,…,bn (1≤bi≤109).
Each of the following m lines contains two integers ui and vi (1≤ui,vi≤n), denoting the ui-th worker can't be assigned to the vi-th piece of equipment. Each pair of ui and vi will be described at most once.
It is guaranteed that there will be at most 10 test cases such that n>100.
The first line contains two integers n and m (1≤n≤4000, 1≤m≤10000), denoting the number of workers/pieces of new equipment and the number of constraints.
The second line contains n integers a1,a2,…,an (1≤ai≤109).
The third line contains n integers b1,b2,…,bn (1≤bi≤109).
Each of the following m lines contains two integers ui and vi (1≤ui,vi≤n), denoting the ui-th worker can't be assigned to the vi-th piece of equipment. Each pair of ui and vi will be described at most once.
It is guaranteed that there will be at most 10 test cases such that n>100.
输出
For each test case, output n lines, the k-th (1≤k≤n) of which containing an integer, denoting the maximum possible total profits for k pairs of workers and pieces of equipment. Note that if it is impossible to find such k pairs, print ''-1'' at this line.
样例输入 复制
2
4 4
10 20 30 40
5 10 7 8
4 2
3 2
1 4
1 2
2 2
1 1
1 1
1 1
1 2样例输出 复制
48
85
115
130
2
-1