Laying Out a Network
Time limit3sMemory limit256 MB
Place n computers and m capacity-limited switches around a circular table; connect every computer to a switch, minimizing total cable length given by circular distance.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Greedy, Intervals, Implementation
- Solved
- No attempts yet
Problem
Holding a programming olympiad raises many problems the organizers must solve. One of them is seating the contestants at computers during the final round of the competition. This time n contestants were invited to the final, and the organizers decided to seat them at a round table. For convenience, the table was divided into n + m identical sectors. Each sector contains either a computer, at which a contestant will sit, or a network switch. The contestants' computers must be connected to switches, and each computer must be connected to exactly one switch. For each switch, the number of computers that can be connected to it is known.
Of course, the organizers want to use as little cable as possible to connect the computers. Suppose that connecting the devices in sectors i and j (1 ≤ i < j ≤ n + m) requires min(j − i, n + m + i - j) meters of cable.
The organizers installed switches in m sectors of the table and placed computers in the remaining n sectors. Now they need to connect the computers to the switches so as to spend as little cable as possible. Help them find the minimum total length of cable that can be used for the connection.
Input
The first line of the input contains the number of test cases T (1 ≤ T ≤ 100). The descriptions of the test cases follow.
Each test case is described as follows. The first line contains two integers n and m (1 ≤ n, m ≤ 300), the number of computers and switches, respectively. The next line contains n + m integers a1, a2, ..., a**n+m (0 ≤ ai ≤ 300), the descriptions of the table's sectors. If a number is 0, the sector contains a computer. Otherwise, the sector contains a switch to which at most ai computers can be connected. It is guaranteed that the total number of computers across all tests does not exceed 300. Likewise, the total number of switches does not exceed 300. It is guaranteed that in every test there is a way to connect all computers to switches.
Output
For each test, output a single number on a separate line: the total length of cable needed to connect the computers to the switches.