Gấu Trúc tại Chợ Trái Cây

Bối cảnh

FullHouse Dev đang giúp Gấu Trúc mua trái cây tại chợ. Có vô số nguồn cung cấp ba loại trái cây khác nhau với giá A, B và C.

Yêu cầu

Gấu Trúc cần mua tổng cộng X trái cây, trong đó phải có ít nhất 2 loại trái cây khác nhau. Hãy giúp Gấu Trúc tìm ra số tiền ít nhất cần chi để mua trái cây.

Input

• Dòng đầu tiên chứa số nguyên T — số lượng bộ test.
• Mỗi bộ test gồm một dòng chứa bốn số nguyên cách nhau bởi dấu cách X, A, B, C — số lượng trái cây cần mua và giá của ba loại trái cây.

Output

• Với mỗi bộ test, in ra số tiền ít nhất cần chi để mua trái cây.

Ràng buộc

• \(1 ≤ T ≤ 10^5\)
• \(2 ≤ X ≤ 1000\)
• \(1 ≤ A, B, C ≤ 100\)

Ví dụ 1

Input

2
2 1 1 1
3 4 3 2

Output

2
7

Giải thích ví dụ

• Test 1: Gấu Trúc có thể mua bất kỳ hai loại trái cây nào với tổng giá là 2.
• Test 2: Gấu Trúc có thể mua 1 trái cây giá 3 và 2 trái cây giá 2, tổng cộng là 7.

Thông tin học tập

• Buổi: B04
• Concepts: for/while loops, multiple test cases
• Giới hạn kiến thức: B01-B04
• Time limit: 2 seconds
• Memory limit: 64 MB
• Point: 25