P17302 [ICPC 2026 Xi'an I] VIP Coupon

Yuki has many fond memories of Chang'an, so she visited a shop intending to buy some souvenirs to take home. The shop sells $n$ souvenirs and $m$ VIP coupons. The price of the $i$-th souvenir is $a_i$, and the $j$-th VIP coupon has a price $b_j$ and a parameter $c_j$. The effect of a VIP coupon with parameter $v$ is as follows: - If the price of the item (including souvenirs and other VIP coupons) purchased immediately after buying this coupon is $x$, the price of that item becomes $\max(x - v, 0)$. The effect of a VIP coupon is mandatory for the very next purchase and cannot be deferred. Clearly, based on this rule, the effects of VIP coupons cannot be stacked. Each item (including souvenirs and VIP coupons) can be purchased $\textbf{at most once}$; they cannot be bought repeatedly. Yuki intends to purchase all souvenirs and any number of VIP coupons (possibly zero) in any order. You need to help Yuki find the minimum cost to purchase all the souvenirs.

The input contains multiple test cases. The first line contains a positive integer $t$ $(1 \le t \le 10^5)$, representing the number of test cases. For each test case: - The first line contains two positive integers $n, m$ $(1 \le n, m \le 5 \cdot 10^5)$. - The second line contains $n$ integers $a_1, \dots, a_n$ $(0 \le a_i \le 10^9)$. - The third line contains $m$ integers $b_1, \dots, b_m$ $(0 \le b_i \le 10^9)$. - The fourth line contains $m$ integers $c_1, \dots, c_m$ $(0 \le c_i \le 10^9)$. It is guaranteed that the sum of $n$ and $m$ over all test cases does not exceed $5 \cdot 10^5$.

For each test case, output a single integer representing the minimum cost to purchase all souvenirs.

For the first test case: - Yuki can purchase the coupons and souvenirs in the following order: 1st coupon, 1st souvenir, 3rd coupon, 2nd souvenir. - After the discounts, the price of the 1st souvenir becomes $0$, and the price of the 2nd souvenir becomes $1$. The total cost is $1 + 0 + 2 + 1 = 4$. For the second test case: - Yuki can purchase the items in the following order: 1st souvenir, 1st coupon, 2nd souvenir, 3rd coupon, 2nd coupon, 3rd souvenir. - After the discounts, the price of the 2nd souvenir becomes $0$, the price of the 2nd coupon becomes $0$, and the price of the 3rd souvenir becomes $1$. The total cost is $2 + 0 + 0 + 2 + 0 + 1 = 5$.