笨蛋同学打算在接下来的 天学习。她有一个“压力值”，初始压力值为 。 第 天，你需要在下面两种行为中选择一种（只能选一种）： 学习：获得 点知识，压力值增加 ； 做博丽灵梦：不获得知识，压力值减少 。如果减少后压力值变成负数，则压力值视为 。 要求在每一天做出选择后，压力值都不超过 （即压力值始终满足 压力值 ）。 请你计算：在最优的安排下，经过这 天后，最多能获得多少知识。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入两个整数 ，表示天数与压力上限。第二行输入 个整数 ，表示第 天学习能获得的知识。第三行输入 个整数 ，表示第 天压力变化的数值。除此之外，保证单个测试文件的 之和不超过 ， 之和不超过 。

输出描述:

对于每一组测试数据，新起一行。输出笨蛋同学最多能获得多少知识。