#1101. Lazy Running

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: tony102

题目描述

在杭州电子科技大学 (HDU),如果你不能在校园跑步 24 圈,就会无法通过体育课。根据规则,你必须保持速度,且你跑步的总距离不能少于 米。

校园中有 4 个打卡点,编号为 。每次你经过一个打卡点时,需要刷卡一次,然后从上一个打卡点到当前打卡点的距离将被添加到你的总跑步距离中。

系统将这 4 个打卡点视为一个循环。当你在打卡点 时,你可以选择跑到 被认为是相邻的)。尽管你可以在两个相邻打卡点之间跑更长的距离,但系统只会记录两打卡点之间的固定距离。

由于 是距离寝室最近的打卡点,Little Q 总是从 开始跑步,并最终以 作为结束点。请你编写一个程序,帮助 Little Q 找到满足总跑步距离不小于 的最短路径。

输入格式

第一行是一个整数 ,表示测试用例的个数。

每个测试用例包含 5 个整数 ,表示所需的最短总跑步距离和打卡点之间的距离。满足以下条件:

输出格式

对于每一个测试用例,输出一个整数,表示满足条件的最小总跑步距离。

样例

输入

1
2000 600 650 535 380

输出

2165