物品供应问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

M公司是一家著名的物资供应公司,具有良好的信誉和客户关系。由于近来受到供应货品价格不稳定和经济不景气的影响,M公司需要制定一个严格的仓储预算。该公司有t个供应季度,每一个季度里,公司的仓储费用预算、该季度的产品价格预算和客户的需求量分别为Pi,Si,Di,Ri,每一个季度里的客户的需求都必须得到满足。除此之外,你也可以在价钱适当的季度里囤积货物,也就是说每个季度里,M公司要用仓库的货物来供应客户,如果货存不够,M公司就要对外购买货物来供应给客户。如果某个季度M公司要购货,那么这个季度还要加上一笔购货预算Ri。例如,有2个季度,P1,S1,D1,R1分别是0,10,100,10;P2,S2,D2,R2分别是0,100,100,10;那么可能的一种方案是:第一季度买够D1的货,第二季度买够D2的货,那么总预算为(D1×S1+R1)+(D2×S2+R2)=(100×10+10)(100×100+10)=11020。还有一种方案是:第一个季度买够D1+D2的货物,第二个季度不用买货而用囤积的货物供货,但是D2的货物要付第一个季度的仓储费,总预算为(S1×(D1+D2)+R1)+P1×D2=(10×(100+100)+10)+0×100=2010,显然第二种方案要优于第一种方案。

人工来进行这样的安排既费时又不够准确,现在M公司希望能有一个程序员来帮他们完成安排货物存购,你能帮帮忙吗?

Input

第1行是一个整数t,表示一共有t个数据,接下来就是这t个数据。每个数据以整数n开头(1<=n<=20),代表有n个季度,然后接着有n行,每行4个整数:Pi,Si,Di,Ri分别代表季度i里公司的仓储费用预算、产品价格预算、客户的需求量和购货预算,1<=i<=n;0<=Pi,Si,Ri<=100000;∑Di<=500。

Output

对应每个数据,输出最小总预算,每个输出占一行。

Sample Input

1
2
0 10 100 10
0 100 100 10

Sample Output

2010

Hint

Source