定义含绝对值的一元一次函数 ，其中 为由外部给定的正整数， 为整数。 现在，对于给定的 个含绝对值的一元一次函数，定义 ，求解 在区间 上的最小值。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：第一行输入三个整数 代表 的数量、值域。此后 行，第 行输入三个整数 用于描述第 个含绝对值的一元一次函数。除此之外，保证所有的 之和不超过 。

输出描述:

对于每一组测试数据，在一行上输出一个整数，代表 在值域上的最小值。