货物运输

题号：NC220553
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

运输公司提供了许多运输方案，每个方案 $P_i$ 会从一个固定的起始城市 $A_i$ 运送东西到另一个固定的终点城市 $B_i$ ，每运输一箱的货物，你就必须付给运输公司 $C_i$ 哒哒币。另外，若两个方案的终点与起点相接，则可以不花任何额外费用的将货物转过去。不过由于你的运输量太大了，运输公司决定祭出优惠，若用方案 $P_i$ 运输了超过 $D_i$ 箱的可鱼果，多出来的部份每箱改收优惠价 $C^,_i$ 哒哒币。

输入描述:

输入的第一行有一个正整数  ，代表测试数据的组数。
每组测试数据的第一行有五个正整数 ，各一个空白隔开。

代表可鱼国内有几个城市， 代表墨鱼运输公司提供几种运输方 案。分别代表你的工厂所在的城市以及你所要送去的城市。代表那隻富有的大可鱼订购了多少箱的货物。

接下来 行，每行有五个正整数 ，意思如同叙述中所说。

输出描述:

每组测试数据输出一行，表示最小的花费

示例1

输入

复制

3
4 4 1 4 1
1 2 1 1 1
2 4 5 1 3
1 3 1 1 1
3 4 6 1 1
4 4 1 4 2
1 2 1 1 1
2 4 5 1 3
1 3 1 1 1
3 4 6 1 1
2 1 1 2 999999999
1 2 50216 1000 50216

输出

复制

6
9
50215999949784