Mô tả bài toán
Bạn là đội trưởng của đội tuyển lập trình trường học, đang dẫn các bạn cùng lớp đến Trùng Khánh để tham gia kỳ thi CCPC. Theo truyền thống của đội, với tư cách là đội trưởng, bạn cần khao các bạn cùng lớp một bữa ăn, và bạn dự định sẽ ăn món đặc sản địa phương là lẩu.
Theo thống kê, trong đội có $x$ sinh viên chỉ ăn được đồ cay, $y$ sinh viên chỉ ăn được đồ không cay, và $z$ sinh viên ăn được cả đồ cay lẫn đồ không cay. Nhà hàng lẩu mà các bạn ghé thăm phục vụ ba loại nồi lẩu:
- Nồi lẩu cay, có thể phục vụ tối đa hai sinh viên ăn được đồ cay, có giá $a$ nhân dân tệ mỗi nồi.
- Nồi lẩu uyên ương (hai ngăn), có thể phục vụ tối đa một sinh viên ăn được đồ cay và tối đa một sinh viên ăn được đồ không cay, có giá $b$ nhân dân tệ mỗi nồi.
- Nồi lẩu không cay, có thể phục vụ tối đa hai sinh viên ăn được đồ không cay, có giá $c$ nhân dân tệ mỗi nồi.
Bạn muốn biết số tiền tối thiểu cần thiết để đảm bảo tất cả sinh viên đều có thể ăn lẩu theo đúng sở thích của mình.
Dữ liệu vào
Có nhiều bộ dữ liệu trong một tệp dữ liệu vào. Dòng đầu tiên của dữ liệu vào chứa một số nguyên $T$ ($1 \le T \le 2025$), cho biết số lượng bộ dữ liệu.
Đối với mỗi bộ dữ liệu:
- Mỗi dòng chứa $6$ số nguyên dương $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$), biểu thị số lượng sinh viên thuộc mỗi nhóm và giá của ba loại nồi lẩu.
Kết quả
Đối với mỗi bộ dữ liệu, in ra một số nguyên duy nhất trên một dòng, biểu thị chi phí tối thiểu có thể để đảm bảo tất cả sinh viên đều được ăn lẩu theo sở thích của mình.
Ví dụ
Dữ liệu vào 1
6 3 1 4 1 5 9 1 1 4 5 1 4 1 5 2 8 2 3 9 6 2 3 5 10 1 5 8 2 8 7 1 9 5 10 3 5
Kết quả 1
8 3 9 39 29 26
Ghi chú
- Trong ví dụ đầu tiên, bạn có thể để tất cả các sinh viên ăn được cả hai loại cùng ăn đồ cay, sau đó gọi ba nồi lẩu cay và một nồi lẩu uyên ương, với tổng chi phí là $1 \times 3 + 5 \times 1 = 8$.
- Trong ví dụ thứ hai, bạn có thể để các sinh viên ăn được cả hai loại chia làm hai người ăn cay và hai người ăn không cay, sau đó gọi ba nồi lẩu uyên ương, với tổng chi phí là $1 \times 3 = 3$.