Description

某公司有个工厂和仓库。由于原材料等价格波动，工厂每个月的生产成本也会波动，令第𝑖个月产品的
单位生产成本为𝑐_𝑖（该月生产一个产品的成本为𝑐_𝑖）。仓库储存产品的也有成本，假设每个月产品的
单位储存成本为固定值1（存储一个产品一个月的成本为1）。令第𝑖个月需要供应给客户的产品数量为
𝑦_𝑖，仓库里的和生产的产品均可供应给客户。假设仓库的容量无限大，供应给客户剩余的产品可储存
在仓库中。若已知𝑛个月中各月的单位生产成本𝑐_𝑖、以及产品供应量𝑦_𝑖，设计一算法决策每个月的产
品生产数量𝑥_𝑖，使得𝑛个月的总成本最低。例如：𝑛=3，𝑐_𝑖:2,5,3，𝑦_𝑖:2,4,5，则𝑥_𝑖:6,0,5，即第
1个月生产6个供应2个（代价2×2=4），储存4个供应给第2个月（代价(2+1)×4=12），第3个月生产5
个供应5个（代价3×5=15），使总成本4+12+15=31最小。

Input

第一行输入T(T<=10)表示有T组数据。每组数据先输入一个正整数N(1<=N<=100000)，表示共有N个月，
接下来输入两行每行N个数，分别表示每个月的成本c_i以及产品需求量y_i。输入保证所有数据均在
int范围内。

Output

输出T行正整数，第i行表示第i组数据下的最小成本。(输出不保证不溢出int)

Sample Input

1
3
2 5 3
2 4 5

Sample Output

31