Kẹo của Tony

Tony vừa thắng giải nhất của một cuộc thi lập trình và muốn mua kẹo mang đến lớp chia cho các bạn. Cửa hàng bán hai loại kẹo: loại 1 giá \(u\) đồng một viên, loại 2 giá \(v\) đồng một viên. Tony cần có đúng \(x\) viên kẹo loại 1 và đúng \(y\) viên kẹo loại 2.

Nghe tin Tony là quán quân, bà chủ tiệm cho phép đổi kẹo: tại quầy, Tony có thể đổi một viên kẹo loại này lấy một viên kẹo loại kia (loại còn lại) và mỗi lần đổi mất thêm \(t\) đồng. Việc đổi có thể thực hiện với số lần tùy ý, trên bất kỳ viên kẹo nào Tony đã mua.

Với mỗi trường hợp mua, hãy tính số tiền ít nhất Tony phải trả để cuối cùng có đủ đúng \(x\) viên loại 1 và \(y\) viên loại 2.

Input

• Dòng đầu tiên chứa số nguyên \(N\) là số trường hợp cần tính.
• \(N\) dòng tiếp theo, mỗi dòng gồm \(5\) số nguyên \(x, y, u, v, t\).

Output

In ra \(N\) dòng, dòng thứ \(i\) là số tiền ít nhất cho trường hợp thứ \(i\).

Constraints

• \(1 \le N \le 19\)
• \(1 \le x, y, u, v, t \le 319\)

Sample Input 1

3
4 3 100 1000 50
5 2 900 200 30
2 6 40 45 10

Sample Output 1

850
1550
350

Explanation

• Trường hợp 1: kẹo loại 2 nên mua bằng cách mua kẹo loại 1 (\(100\)) rồi đổi (\(+50\)) tốn \(150\), rẻ hơn giá \(1000\). Tổng: \(4 \cdot 100 + 3 \cdot 150 = 850\).
• Trường hợp 2: kẹo loại 1 nên mua bằng cách mua kẹo loại 2 (\(200\)) rồi đổi (\(+30\)) tốn \(230\), rẻ hơn \(900\). Tổng: \(5 \cdot 230 + 2 \cdot 200 = 1550\).
• Trường hợp 3: mua thẳng cả hai loại vẫn rẻ nhất cho loại 1 (\(40\) so với \(45 + 10\)), còn loại 2 thì \(45 < 40 + 10\). Tổng: \(2 \cdot 40 + 6 \cdot 45 = 350\).