U501201 E.G.O.绽放：山茶花

只是聆听着风的凌乱。 翻阅了命运的启示，眺望着今夜的星辰。 于无尽的因果中仅看见了无数轮皓月。 握不住星光，正如双手抓不到未来与往昔。 正是春日花繁时，理想遍地。 铳声宣告了新的启示，山茶花于枪口盛放。 风拂过了脸颊，繁花埋没了笑颜。 那是漫山遍野的星光。

无数棵凋零的山茶花树，在秋风中萧瑟。 随之飘落的碎花，散乱在地，只知其数。 李箱抚着秋风，望着零落的残花有些离枝，挂于他树；有些卷去，漫过道路；有些则凝立不语，挂于枝头，与离枝无异。但碎裂的花，却仍仅向东飘去，无愿回望西处的李箱。 李箱转头，询问了您一个问题：“执行经理，您说如若我基于您每段路上的茶花数，与茶树的位置，您能评估出某种最优方案，让所有山茶花树，绽放的花数最多的树，绽放的花数最少吗？我的意思是，我不想让东柏遭受如此苦痛……” 辛克莱决定帮您凝练题意：“**给定一数组和某些特殊位置，您可给数组的特殊位置减值，要求使该数组任意前缀和非正数，询问特殊位置加值的最大值最小的方案。**” 浮士德和您都立即想出了最优方案，您们想要核对答案，于是您轻轻念道：“所谓的最大值最小，该值是：……”

第一行输入整数 $T$ ，代表测试组数。 对于每组测试的第一行，输入整数 $n$ 和 $m$，代表道路的段数和山茶树的位置。 接下来一行，输入每段道路上，山茶花的数量 $a_i$。 再接下来一行，输入每棵山茶花的位置 $b_i$。

对于每组测试，输出一个整数 $ans$，如题意所述。

对于30%的数据，$1 \le n \le 10^3$，$1 \le \sum{n} \e 10^3$. 对于70%的数据，$1 \le n \le 10^6$，$1 \le \sum{n} \le 10^6$. 对于100%的数据，$1 \le n \le 10^7$，$1 \le \sum{n} \le 10^7$,$1 \le T \le 10^2$,$0 \le k \le n$，$1\le a_i \le 10^9$，$0 \le b_i \le max{\ a_i}$. 输入输出交互量较大，请选手注意自己的IO方式。