I-Reinforced Problem_2024年华东交通大学“双基”程序设计竞赛

时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

原神是一款开放世界的动作角色扮演游戏，玩家一次可以选择四名角色参与战斗，并且在战斗中可以快速切换。角色可以通过各种方式增强他们的力量，例如提高角色的等级，改进角色装备的圣遗物和武器。

$\text{zml}$ 就是一名忠实的原神玩家，但是由于 $\text{ffg}$ 对原神的强烈抵制， $\text{zml}$ 不得不规划一下自己玩原神的时间。

$\text{zml}$ 第 $i$ 天玩原神都会有一个喜悦值 $a_i$ ，与此同时， $\text{ffg}$ 也会在这天有一个对原神玩家的愤怒值 $b_i$ ，并且假如 $\text{zml}$ 连续几天玩原神这个愤怒值会累加，假如有一天没有玩原神， $\text{ffg}$ 就会原谅他，然后愤怒值清空，但是 $\text{zml}$ 的喜悦值不会受到影响。

$\text{ffg}$ 有个忍耐值 $m$ ，只要 $\text{ffg}$ 的愤怒值没有超过 $m$ ， $\text{ffg}$ 就不会爆发， $\text{zml}$ 就可以安然无恙的玩原神，否则 $\text{ffg}$ 就会把他炖了。

现在基于 $\text{zml}$ 每天的喜悦值和 $\text{ffg}$ 对原神玩家的愤怒值，请你输出 $\text{zml}$ 的最大喜悦值（当然， $\text{zml}$ 不想被炖）。

输入描述:

第一行包含一个整数 ，表示测试用例的数量。

每个测试用例的第一行包含一个整数 ， 表示天数， 表示  的最大愤怒值。

第二行包含  个数 ，表示  在第  天的喜悦值 。

第三行包含  个数 ，表示  在第  天的愤怒值 。

保证所有测试用例的  加起来的和不超过 。

输出描述:

对于每个测试用例，输出一个整数，表示  玩原神的最大喜悦值（不被邪恶的  炖的前提下）。

示例1

输入

复制

输出

复制

说明

对于样例 ， 会选择第  天，第  天和第  天

- 第  天  的愤怒值为 ， 的喜悦值为 。

- 第  天由于  不选择玩原神，所以  的愤怒值降为 ， 的喜悦值仍然为 。

- 第  天  的愤怒值为 ， 的喜悦值为 。

- 第  天  的愤怒值为 ， 的喜悦值为 。

为什么  不选择第  天，第  天和第  天呢？这连续  天的愤怒值之和是 。

这是因为假如选择第  天，第  天和第  天， 在第  天愤怒值为 ， 就会把  炖了，也就是说，假如  的愤怒值中途大于 ，即使后面降下来了也无济于事。

示例2

输入

复制

5
6 9
2 4 3 1 5 1
9 1 1 1 -4 2
5 16
8 7 8 4 -1
1 6 6 7 9
5 7
1 1 -1 -2 8
7 -5 9 3 1
6 6
5 8 -2 8 5 -4
7 -5 5 1 5 -2
4 15
-3 3 5 8
-3 10 7 -3

输出

复制