시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 256 MB111100.000%

문제

При проведении олимпиад по программированию возникает множество задач, которые необходимо решить организаторам. Одна из таких задач — размещение участников за компьютерами во время финального тура соревнования. В этот раз на финал соревнования пригласили n участников и их решили посадить за круглый стол. Для удобства стол разбили на n + m одинаковых секторов. В каждом секторе расположен либо компьютер, за которым будет сидеть участник, либо сетевой коммутатор. Компьютеры участников должны быть подключены к коммутаторам, каждый компьютер должен быть подключен ровно к одному коммутатору. Про каждый коммутатор известно, сколько компьютеров можно к нему подключить.

Конечно, организаторы хотят использовать для подключения компьютеров как можно меньше кабеля. Будем считать, что для соединения устройств в секторах i и j (1 ≤ i < j ≤ n + m) требуется min(j − in + m + i - j) метров кабеля.

Организаторы установили коммутаторы в m секторов стола и разместили в остальных n секторах компьютеры. Теперь им необходимо выполнить подключение компьютеров к коммутаторам, чтобы потратить как можно меньше кабеля. Помогите им выяснить, какую минимальную суммарную длину кабеля можно использовать для подключения.

입력

В первой строке входных данных записано количество тестовых наборов T (1 ≤ T ≤ 100). Далее идет описание тестовых наборов.

Каждый тестовый набор описывается следующим образом. В первой строке записано два целых числа n и m (1 ≤ nm ≤ 300) — количество компьютеров и коммутаторов, соответственно. В следующей строке записано n + m целых чисел a1a2, ..., an+m (0 ≤ ai ≤ 300) — описания секторов стола. Если очередное число равно 0, то в этом секторе находится компьютер. Иначе, в секторе находится коммутатор, к которому можно подключить максимум ai компьютеров. Гарантируется, что общее количество компьютеров во всех тестах не превышает 300. Аналогично, общее количество коммутаторов не превышает 300. Гарантируется, что во всех тестах существует способ подключить все компьютеры к коммутаторам.

출력

Для каждого теста в отдельной строке выведите одно число — суммарную длину кабеля, необходимого для подсоединения компьютеров к коммутаторам.

예제 입력 1

1
5 2
3 0 0 4 0 0 0

예제 출력 1

6