คำอธิบายโจทย์

คุณเป็นกัปตันทีมแข่งขันเขียนโปรแกรมของโรงเรียน ซึ่งกำลังนำเพื่อนร่วมชั้นเดินทางไปยังฉงชิ่งเพื่อเข้าร่วมการแข่งขัน CCPC ตามธรรมเนียมของทีม ในฐานะกัปตัน คุณจะต้องเลี้ยงอาหารเพื่อนร่วมชั้นหนึ่งมื้อ และคุณวางแผนที่จะไปกินอาหารขึ้นชื่อของท้องถิ่น นั่นคือหม้อไฟ

จากสถิติพบว่า ในทีมมีนักเรียน $x$ คนที่กินได้เฉพาะอาหารเผ็ด, นักเรียน $y$ คนที่กินได้เฉพาะอาหารไม่เผ็ด และนักเรียน $z$ คนที่กินได้ทั้งอาหารเผ็ดและอาหารไม่เผ็ด ร้านหม้อไฟที่คุณไปมีหม้อให้เลือก 3 ประเภท:

• หม้อซุปเผ็ด ซึ่งสามารถรองรับนักเรียนที่กินเผ็ดได้สูงสุดสองคน มีราคาหม้อละ $a$ หยวน
• หม้อซุปผสม (สองช่อง) ซึ่งสามารถรองรับนักเรียนที่กินเผ็ดได้สูงสุดหนึ่งคน และนักเรียนที่กินไม่เผ็ดได้สูงสุดหนึ่งคน มีราคาหม้อละ $b$ หยวน
• หม้อซุปไม่เผ็ด ซึ่งสามารถรองรับนักเรียนที่กินไม่เผ็ดได้สูงสุดสองคน มีราคาหม้อละ $c$ หยวน

คุณต้องการทราบจำนวนเงินขั้นต่ำที่ต้องใช้เพื่อให้มั่นใจว่านักเรียนทุกคนจะได้กินหม้อไฟตามความชอบของตนเอง

ข้อมูลนำเข้า

มีหลายกรณีทดสอบในไฟล์ข้อมูลนำเข้าเดียว บรรทัดแรกของข้อมูลนำเข้าประกอบด้วยจำนวนเต็ม $T$ ($1 \le T \le 2025$) ซึ่งระบุจำนวนกรณีทดสอบ

สำหรับแต่ละกรณีทดสอบ:

• แต่ละบรรทัดประกอบด้วยจำนวนเต็มบวก $6$ จำนวน ได้แก่ $x, y, z, a, b, c$ ($1 \le x, y, z, a, b, c \le 2025$) แทนจำนวนนักเรียนในแต่ละกลุ่มและราคาของหม้อไฟทั้งสามประเภท

ข้อมูลส่งออก

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์จำนวนเต็มหนึ่งจำนวนในหนึ่งบรรทัด แทนค่าใช้จ่ายขั้นต่ำที่เป็นไปได้เพื่อให้มั่นใจว่านักเรียนทุกคนจะได้กินหม้อไฟตามความชอบของตนเอง

ตัวอย่าง

ข้อมูลนำเข้าตัวอย่าง 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

ข้อมูลส่งออกตัวอย่าง 1

8
3
9
39
29
26

หมายเหตุ

• ในตัวอย่างแรก คุณสามารถให้นักเรียนที่กินได้ทั้งสองแบบทุกคนกินเผ็ด จากนั้นสั่งหม้อซุปเผ็ด 3 หม้อ และหม้อซุปผสม 1 หม้อ โดยมีค่าใช้จ่ายรวมเป็น $1 \times 3 + 5 \times 1 = 8$
• ในตัวอย่างที่สอง คุณสามารถให้นักเรียนที่กินได้ทั้งสองแบบแบ่งเป็นกินเผ็ด 2 คน และกินไม่เผ็ด 2 คน จากนั้นสั่งหม้อซุปผสม 3 หม้อ โดยมีค่าใช้จ่ายรวมเป็น $1 \times 3 = 3$