ชมรมลูบไล้คาปิบารานานาชาติกำลังเตรียมเสื้อยืดสำหรับงานกิจกรรมหนึ่ง โดยมีสี่ขนาด ได้แก่ S, M, L และ XL เรียงตามลำดับจากเล็กไปใหญ่ จำนวนเสื้อยืดที่ต้องการคือ $n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ และ $n_{\mathrm{XL}}$ ตามลำดับ ที่ความเข้มสีมาตรฐาน เสื้อยืดขนาด S, M, L และ XL ต้องใช้สีย้อม $B$, $Br$, $Br^2$ และ $Br^3$ หน่วย ตามลำดับ

เครื่องย้อมผ้าใช้ความเข้มเป็นจำนวนเต็ม $x$ ความเข้มสีต่ำสุดที่อนุญาตคือ $P$ และ $x = K$ คือความเข้มมาตรฐาน ดังนั้น $x$ ต้องสอดคล้องกับเงื่อนไข $P \le x \le K$ หากเสื้อยืดตัวหนึ่งต้องใช้สีย้อม $q$ หน่วยที่ความเข้มมาตรฐาน การย้อมเสื้อตัวนั้นที่ความเข้ม $x$ จะใช้สีย้อม $\lceil qx/K \rceil$ หน่วย เสื้อยืดทุกตัวต้องใช้ความเข้ม $x$ เท่ากันทั้งหมด

กำหนดให้มีสีย้อม $A$ หน่วย จงหาความเข้ม $x$ ที่มากที่สุดที่เป็นไปได้ ซึ่งทำให้สามารถย้อมเสื้อยืดทั้งหมดได้โดยใช้สีย้อมไม่เกิน $A$ หน่วย หากไม่มี $x$ ดังกล่าว ให้แสดงผลเป็น $-1$

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

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

$$ n_{\mathrm{S}} \ n_{\mathrm{M}} \ n_{\mathrm{L}} \ n_{\mathrm{XL}} \ r \ A \ B \ P \ K $$

$n_{\mathrm{S}}$, $n_{\mathrm{M}}$, $n_{\mathrm{L}}$ และ $n_{\mathrm{XL}}$ แทนจำนวนเสื้อยืดขนาด S, M, L และ XL ตามลำดับ ($0 \le n_{\mathrm{S}}, n_{\mathrm{M}}, n_{\mathrm{L}}, n_{\mathrm{XL}} \le 10^5$ และ $n_{\mathrm{S}} + n_{\mathrm{M}} + n_{\mathrm{L}} + n_{\mathrm{XL}} \ge 1$)

ค่า $r$ แทนตัวคูณที่ปริมาณสีย้อมที่ต้องการที่ความเข้มมาตรฐานจะเพิ่มขึ้นทุกครั้งที่ขนาดเสื้อเพิ่มขึ้นหนึ่งระดับ ($1 \le r \le 10$)

$A$ แทนปริมาณสีย้อมทั้งหมดที่มีอยู่ มีหน่วยเป็นหน่วย ($0 \le A \le 10^{15}$)

$B$ แทนปริมาณสีย้อมที่ต้องใช้ในการย้อมเสื้อยืดขนาด S หนึ่งตัวที่ความเข้มมาตรฐาน มีหน่วยเป็นหน่วย ($1 \le B \le 10^6$)

$P$ แทนความเข้มสีต่ำสุดที่อนุญาต และ $K$ แทนความเข้มสีมาตรฐาน ($1 \le P \le K \le 10^9$)

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

สำหรับแต่ละชุดทดสอบ ให้แสดงผลจำนวนเต็ม $x$ ที่มากที่สุดที่ทำให้ $P \le x \le K$ และสามารถย้อมเสื้อยืดทั้งหมดได้โดยใช้สีย้อมอย่างมาก $A$ หน่วย หากไม่มีจำนวนเต็มดังกล่าว ให้แสดงผลเป็น $-1$

ตัวอย่าง

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

3
1 1 1 1 2 15 2 1 12
2 0 1 0 3 8 2 4 10
0 0 0 1 10 1000 1 900000 999999

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

6
-1
999999