В соревновании по арифметике нужно уметь набирать наибольшую возможную сумму из имеющихся у участников карточек. Так, в команде «fst_ezik» у Вадима есть $$$n$$$ карточек с числами $$$a_i$$$, а у Кости — $$$m$$$ карточек с числами $$$b_i$$$. В каждом из $$$q$$$ раундов они хотят победить, но в этот раз правила соревнования немного отличаются от обычных.
В каждом раунде участникам даются три числа $$$x_i$$$, $$$y_i$$$ и $$$z_i$$$. Команда «fst_ezik» должна выбрать ровно $$$z_i$$$ карточек из всех имеющихся у них, но Вадим может выбрать не больше $$$x_i$$$ карточек из своего набора, а Костя — не больше $$$y_i$$$ карточек из своего набора. Помогите им найти наибольшую возможную сумму для каждого из $$$q$$$ раундов.
Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ $$$(1 \le t \le 10^4)$$$ — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке каждого набора данных даны три целых числа $$$n$$$, $$$m$$$, $$$q$$$ $$$(1 \le n, m \le 2 \cdot 10^5, 1 \le q \le 10^5)$$$ — количество карточек у Вадима, количество карточек у Кости и количество раундов в соревновании.
Во второй строке даны $$$n$$$ целых чисел $$$a_i$$$ $$$(1 \le a_i \le 10^9)$$$ — числа на карточках Вадима.
В третьей строке даны $$$m$$$ целых чисел $$$b_i$$$ $$$(1 \le b_i \le 10^9)$$$ — числа на карточках Кости.
В следующих $$$q$$$ строках описываются раунды тремя целыми числами $$$x_i$$$, $$$y_i$$$, $$$z_i$$$ $$$(0 \le x_i \le n, 0 \le y_i \le m, 0 \le z_i \le x_i + y_i)$$$ — ограничение на количество карточек Вадима, ограничение на количество карточек Кости и количество карточек, которое нужно выбрать им двоим.
Гарантируется, что сумма $$$n$$$ по всем наборам данных не превосходит $$$2 \cdot 10^5$$$, сумма $$$m$$$ по всем наборам данных не превосходит $$$2 \cdot 10^5$$$, сумма $$$q$$$ по всем наборам данных не превосходит $$$10^5$$$.
Для каждого набора входных данных выведите $$$q$$$ чисел — наибольшую возможную сумму для соответствующего раунда.
43 4 510 20 301 2 3 40 0 03 4 73 4 41 4 42 2 45 5 2500000000 300000000 100000000 900000000 700000000800000000 400000000 1000000000 600000000 2000000001 4 35 2 64 4 1100 100 20 20100 100 20 204 4 53 3 62 363 711286 121 1021 1 13 1 11 2 01 3 20 1 03 3 3
0 70 64 39 57 2700000000 4200000000 420 711 711 0 997 0 1360
| Codeforces Round 1043 (Div. 3) |
|---|
| Закончено |
