Tony đã giành chiến thắng và nhận giải thưởng của anh Hiếu. Tony dự định mua quà về để tặng cho các bạn trong lớp của mình. Tony dự dịnh sẽ mua hai loại kẹo về để tặng các bạn. Tony mua \(x\) cái kẹo loại thứ nhất và \(y\) cái kẹo loại thứ \(2\). Loại kẹo thứ nhất có giá là \(u\) đồng cái, loại thứ hai có giá \(v\) đồng một cái. Bà chủ quán cũng là người yêu thích lập trình, biết rằng Tony vừa mới đc thưởng của anh Hiếu vì học giỏi nên khuyến mãi thêm cho Tony một tùy chọn. Đó là sau khi mua, Tony có thể đổi một cái kẹo loại này lấy một cái kẹo loại kia với chi phí đổi là \(t\) đồng.

Bạn hãy lập trình giúp Tony tính số tiền ít nhất phải trả để mua kẹo nếu bạn ấy mua theo cách tối ưu nhất. Nhất định Tony phải mua đúng \(x\) cái loại \(1\) và \(y\) cái loại \(2\).

INPUT FORMAT

Dòng đầu tiên là \(N\)- các trường hợp mua kẹo mà Tony cần tính \((1 \leq N \leq 20)\).

\(N\) dòng sau: Mỗi dòng là \(x,y,u,v,t\) số nguyên \((1 \leq x,y,u,v,t \leq 320)\).

OUTPUT FORMAT

In ra màn hình \(N\)dòng, mỗi dòng là số tiền ít nhất cần trả cho một trường hợp.

Ví dụ:

Input

2
2 2 500 1000 500
3 5 500 600 100

Output

3000
4500

Trường hợp \(1\): Tony mua \(2\) cái loại \(1\) hết \(1000\), \(2\) cái loại \(2\) hết \(2000\). Tổng là \(3000\).

Trường hợp \(2\): Tony mua \(3\) cái loại \(1\) hết \(500\), \(5\) cái loại \(2\) hết \(3000\). Tổng là \(4500\).

Lời giải bài tập này: Tại đây

Group giải đáp thắc mắc: Lập trình 24h

Fanpage CLB: CLB lập trình Full House- Việt Nam

Youtube: CLB Lập Trình Full House