D. Филин Серафим
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Ребята выстроились в очередь из $$$n$$$ человек, начинающуюся с человека под номером $$$i = 1$$$, чтобы узнать у филина Серафима, в чем смысл жизни. К сожалению, Кирилл был очень занят написанием легенды к этой задаче, поэтому пришел чуть позже и встал в конец очереди после $$$n$$$-го человека. Кирилла такое положение совершенно не устраивает, поэтому он решил подкупить некоторых людей впереди себя.

Для $$$i$$$-го человека в очереди Кирилл знает два значения: $$$a_i$$$ и $$$b_i$$$. Если в данный момент Кирилл стоит на позиции $$$i$$$, то он может выбрать любую позицию $$$j$$$ такую, что $$$j < i$$$ и поменяться с человеком на позиции $$$j$$$ местами. При этом Кириллу придется заплатить ему $$$a_j$$$ монет. А для каждого $$$k$$$ такого, что $$$j < k < i$$$ Кириллу придется заплатить $$$b_k$$$ монет человеку на позиции $$$k$$$. Кирилл может выполнить это действие любое количество раз.

Кирилл человек бережливый, поэтому он хочет потратить как можно меньше монет, но он не хочет ждать слишком долго, поэтому Кирилл считает должен оказаться среди первых $$$m$$$ человек в очереди.

Помогите Кириллу определить минимальное количество монет, которое ему придется потратить, чтобы не ждать слишком долго.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le m \le n \le 200\,000$$$) — количество людей в очереди помимо Кирилла и максимальная допустимая финальная позиция Кирилла соответственно.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$).

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^9$$$).

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

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

Пример
Входные данные
4
4 2
7 3 6 9
4 3 8 5
6 2
6 9 7 1 8 3
5 8 8 1 4 1
7 7
7 2 9 2 6 5 9
9 1 10 7 1 4 9
2 1
2 3
1 1
Выходные данные
14
22
9
3