贪心，区间合并（Python）

思路：贪心 + 区间合并。首先看数据量，用dp肯定过不了，那就考虑贪心；接下来把x和h进行排序，也就是用(x, h)进行自定义排序；然后进行区间合并操作，具体来说就是用栈进行模拟，模拟完后得到合并的多段区间。最终，按照区间长度进行降序排列，选择前m个长度最大的区间，加起来就是答案了

代码：

import sys
input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

def solve():
    n, m = MII()
    h = LII()
    x = LII()

    a = sorted(zip(x, h))

    st = []
    for pos, h in a:
        cur_r = pos + h

        if not st or st[-1][0] < pos:
            st.append([cur_r, 1])
        else:
            st[-1][0] = fmax(st[-1][0], cur_r)
            st[-1][1] += 1

    res = [size for r, size in st]
    res.sort(reverse=True)

    ans = sum(res[:fmin(m, len(res))])
    print(ans)

# t = 1
t = II()
for _ in range(t):
    solve()