写作业

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

题目描述

我们都是独立完成作业的好孩子

有 $A$ 、 $B$ 两个同学，他们是好朋友。由于作业太多，他们经常在晚自习互帮互助。现在有 $2$ 科作业：分别是数学，语文。

$A$ 独立完成数学需要 $a_1$ 分钟，独立完成语文需要 $b_1$ 分钟。同理 $B$ 独立完成数学需要 $a_2$ 分钟，独立完成语文需要 $b_2$ 分钟。

但这样太慢了，于是他们打算互相借鉴一下作业，这样可以节约一半的时间。（比如 $B$ 写了数学，而 $A$ 还没写，那 $A$ 就只需要 $\frac{a_1}{2}$ 分钟完成数学）。但 $A$ 、 $B$ 写作业都有个特点，就是开始独立这项写作业后绝对不借鉴。即：

1. 自己写，没写完前坚决不借鉴
2. 拿别人写完的来借鉴
3. 什么都不干，时间流逝

求两人都写完作业最少时间

输入描述:

第一行输入一个整数 ，代表多组数据的组数。

随后  行每行  个整数 ，，，，代表 、 所需要花费的时间。

数据保证 ，，并保证  均为偶数。

输出描述:

对于每组数据输出一个整数代表答案。

示例1

输入

复制

1
10 20 20 6

输出

复制

说明

 同学先完成数学作业，花费时间  分钟，同时  同学先完成语文作业，花费时间  分钟。

 分钟时， 同学借鉴  同学的语文作业，花费时间  分钟， 同学借鉴  同学数学作业，花费时间  分钟。

在第  分钟时，两人均完成作业。