题目描述

工程师们正在为一幢大楼设计一个照明系统。经过他们的设计规则，整个大楼需要 \(n\) 种照明灯，每种照明灯需要的电压各不相同，整个系统还需要为每种电压的照明灯配备一个单独的电源系统。当然在可以节约资金的情况下，某些低电压的照明灯可以用高电压的照明灯替换。现在给出每种电压值、电源系统的价格、每种照明灯需要的数量和价格，求最低的总价格。

格式

输入格式

第一行为正整数 \(t(≤10)\)，表示数据组数；每组数据中，第一行为正整数 \(n(≤ 500)\)，表示照明灯的种类数，接下来 \(n\) 行，每行四个正整数 \(V(≤2000)、K(≤1000)、 C(≤20)\) 和 \(L(≤100)\)，分别表示电压值、电源系统的价格、照明灯的单价和数量需求，数据保证所有照明灯的电压值各不相同。

输出格式

对于每组数据，输出最低总价。

样例1

输入样例1

1
3
100 500 10 20
120 600 8 16
220 400 7 18

输出样例1

778

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T3\)

文件IO

freopen("lamps.in","r",stdin);
freopen("lamps.out","w",stdout);