D เพิ่งพบเกมเล็ก ๆ เกมหนึ่งบนอินเทอร์เน็ต มีกฎดังต่อไปนี้:
- เป้าหมายของเกมคือฆ่ามังกร $n$ ตัวตามลำดับหมายเลข $1$ ถึง $n$ มังกรแต่ละตัวมีพลังชีวิตเริ่มต้น $a_i$ และมีความสามารถฟื้นฟู เมื่อใช้ความสามารถนี้ พลังชีวิตจะเพิ่มขึ้นครั้งละ $p_i$ จนไม่เป็นลบ มังกรจะตายได้เฉพาะหลังการโจมตีสิ้นสุดลงและเมื่อพลังชีวิตเท่ากับ $0$ พอดีเท่านั้น
- ตอนเริ่มเกม ผู้เล่นมีดาบ $m$ เล่มที่ทราบพลังโจมตี เมื่อต่อสู้กับมังกรแต่ละตัว ผู้เล่นเลือกดาบได้เพียงหนึ่งเล่ม หลังฆ่ามังกร ดาบนั้นจะหายไป แต่ผู้เล่นจะได้รับดาบเล่มใหม่เป็นรางวัล
D รู้สึกว่าเกมนี้น่าเบื่อมาก แต่ผู้เล่นที่ผ่านเกมเร็วที่สุดจะได้สิทธิ์เข้าแข่งขัน ION2018 ดังนั้น D จึงตัดสินใจเขียนหุ่นยนต์ซื่อ ๆ เพื่อช่วยเธอผ่านเกม หุ่นยนต์ที่เธอเขียนทำตามกฎดังนี้:
- เมื่อเผชิญมังกรแต่ละตัว หุ่นยนต์จะเลือกดาบที่มีพลังโจมตีมากที่สุดในบรรดาดาบที่มีอยู่และมีพลังโจมตีไม่เกินพลังชีวิตเริ่มต้นของมังกร หากไม่มีดาบเช่นนั้น จะเลือกดาบที่มีพลังโจมตีน้อยที่สุดเป็นอาวุธ
- เมื่อต่อสู้กับมังกรแต่ละตัว หุ่นยนต์จะใช้ดาบที่เลือกในขั้นก่อนหน้าโจมตีจำนวนคงที่ $x$ ครั้ง ทำให้พลังชีวิตมังกรลดลง $x \times ATK$
- จากนั้นมังกรจะใช้ความสามารถฟื้นฟูซ้ำ ๆ โดยฟื้นพลังชีวิตครั้งละ $p_i$ หากพลังชีวิตเท่ากับ $0$ ก่อนใช้ความสามารถฟื้นฟู หรือหลังฟื้นฟูครั้งใดครั้งหนึ่ง มังกรจะตายและผู้เล่นผ่านด่านนี้
เห็นได้ชัดว่าจำนวนครั้งที่หุ่นยนต์โจมตีเป็นกุญแจสำคัญต่อการผ่านเกมให้เร็วที่สุด ตอนนี้ D ทราบคุณสมบัติทั้งหมดของมังกรทุกตัวแล้ว เธออยากทดสอบคุณว่า ควรตั้งจำนวนครั้งโจมตี $x$ ของหุ่นยนต์เป็นเท่าใด จึงจะผ่านเกมด้วยจำนวนการโจมตีน้อยที่สุด
แน่นอนว่าหากตั้งค่าอย่างไรก็ไม่สามารถผ่านเกมได้ ให้พิมพ์ -1
ข้อมูลนำเข้า
อ่านข้อมูลจากไฟล์ dragon.in
บรรทัดแรกมีจำนวนเต็ม $T$ แทนจำนวนชุดข้อมูล
จากนั้นเป็นข้อมูล $T$ ชุด แต่ละชุดมี 5 บรรทัด
- บรรทัดแรกของแต่ละชุดมีจำนวนเต็มสองจำนวน $n,m$ แทนจำนวนมังกรและจำนวนดาบเริ่มต้น
- บรรทัดถัดมามีจำนวนเต็มบวก $n$ จำนวน จำนวนที่ $i$ แทนพลังชีวิตเริ่มต้น $a_i$ ของมังกรตัวที่ $i$
- บรรทัดถัดมามีจำนวนเต็มบวก $n$ จำนวน จำนวนที่ $i$ แทนความสามารถฟื้นฟู $p_i$ ของมังกรตัวที่ $i$
- บรรทัดถัดมามีจำนวนเต็มบวก $n$ จำนวน จำนวนที่ $i$ แทนพลังโจมตีของดาบรางวัลหลังฆ่ามังกรตัวที่ $i$
- บรรทัดถัดมามีจำนวนเต็มบวก $m$ จำนวน แทนพลังโจมตีของดาบ $m$ เล่มที่มีตอนเริ่มต้น
ข้อมูลส่งออก
เขียนผลลัพธ์ลงไฟล์ dragon.out
มีทั้งหมด $T$ บรรทัด
บรรทัดที่ $i$ มีจำนวนเต็มหนึ่งจำนวน แทนจำนวนครั้งโจมตี $x$ น้อยที่สุดที่ทำให้หุ่นยนต์ผ่านเกมสำหรับข้อมูลชุดที่ $i$ หากไม่มีคำตอบ ให้พิมพ์ -1
ตัวอย่าง
ข้อมูลนำเข้า 1
2 3 3 3 5 7 4 6 10 7 3 9 1 9 1000 3 2 3 5 6 4 8 7 1 1 1 1 1
ข้อมูลส่งออก 1
59 -1
หมายเหตุ
ข้อมูลชุดแรก:
- ตอนเริ่มต้น ดาบที่มีมีพลังโจมตี $\{1,9,10\}$ มังกรตัวที่ $1$ มีพลังชีวิต $3$ จึงเลือกดาบพลังโจมตี $1$ โจมตี $59$ ครั้ง สร้างความเสียหาย $59$ ขณะนั้นพลังชีวิตมังกรเป็น $-56$ หลังฟื้นฟู $14$ ครั้ง พลังชีวิตเป็น $0$ พอดีและตาย
- ดาบพลังโจมตี $1$ หายไป และเก็บดาบพลังโจมตี $7$ มา ตอนนี้ดาบที่มีมีพลังโจมตี $\{7,9,10\}$ มังกรตัวที่ $2$ มีพลังชีวิต $5$ จึงเลือกดาบพลังโจมตี $7$ โจมตี $59$ ครั้ง สร้างความเสียหาย $413$ ขณะนั้นพลังชีวิตมังกรเป็น $-408$ หลังฟื้นฟู $68$ ครั้ง พลังชีวิตเป็น $0$ พอดีและตาย
- ตอนนี้ดาบที่มีมีพลังโจมตี $\{3,9,10\}$ มังกรตัวที่ $3$ มีพลังชีวิต $7$ จึงเลือกดาบพลังโจมตี $3$ โจมตี $59$ ครั้ง สร้างความเสียหาย $177$ ขณะนั้นพลังชีวิตมังกรเป็น $-170$ หลังฟื้นฟู $17$ ครั้ง พลังชีวิตเป็น $0$ พอดีและตาย
- ไม่มีวิธีผ่านเกมที่โจมตีน้อยกว่า $59$ ครั้ง ดังนั้นคำตอบคือ $59$
ข้อมูลชุดที่สอง:
- ไม่มีวิธีที่ฆ่าได้ทั้งมังกรตัวแรกและตัวที่สอง จึงผ่านเกมไม่ได้ และพิมพ์
-1
ตัวอย่าง 2
ดูไฟล์ dragon/dragon2.in และ dragon/dragon2.ans ในไดเรกทอรีของผู้เข้าแข่งขัน
งานย่อย
| หมายเลขกรณีทดสอบ | $n$ | $m$ | $p_i$ | $a_i$ | พลังโจมตี | ข้อจำกัดอื่น |
|---|---|---|---|---|---|---|
| $1$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | ไม่มี |
| $2$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $=1$ | ไม่มี |
| $3$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | ไม่มี |
| $4$ | $\le 10^5$ | $=1$ | $=1$ | $\le 10^5$ | $\le 10^5$ | ไม่มี |
| $5$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | คุณสมบัติ 1 และ 2 |
| $6$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | คุณสมบัติ 1 และ 2 |
| $7$ | $\le 10^3$ | $\le 10^3$ | $\le 10^5$ | $\le 10^5$ | $\le 10^5$ | คุณสมบัติ 1 และ 2 |
| $8$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | คุณสมบัติ 1 |
| $9$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | คุณสมบัติ 1 |
| $10$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | คุณสมบัติ 1 |
| $11$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | คุณสมบัติ 1 |
| $12$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | คุณสมบัติ 1 |
| $13$ | $=1$ | $=1$ | $\le 10^8$ | $\le 10^8$ | $\le 10^6$ | คุณสมบัติ 1 |
| $14$ | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | ไม่มีข้อจำกัดพิเศษ |
| $15$ | $=10^5$ | $=10^5$ | $=1$ | $\le 10^8$ | $\le 10^6$ | ไม่มีข้อจำกัดพิเศษ |
| $16$ | $\le 10^5$ | $\le 10^5$ | $p_i$ ทุกค่าเป็นจำนวนเฉพาะ | $\le 10^{12}$ | $\le 10^6$ | คุณสมบัติ 1 |
| $17$ | $\le 10^5$ | $\le 10^5$ | $p_i$ ทุกค่าเป็นจำนวนเฉพาะ | $\le 10^{12}$ | $\le 10^6$ | คุณสมบัติ 1 |
| $18$ | $\le 10^5$ | $\le 10^5$ | ไม่มีข้อจำกัดพิเศษ | $\le 10^{12}$ | $\le 10^6$ | คุณสมบัติ 1 |
| $19$ | $\le 10^5$ | $\le 10^5$ | ไม่มีข้อจำกัดพิเศษ | $\le 10^{12}$ | $\le 10^6$ | คุณสมบัติ 1 |
| $20$ | $\le 10^5$ | $\le 10^5$ | ไม่มีข้อจำกัดพิเศษ | $\le 10^{12}$ | $\le 10^6$ | คุณสมบัติ 1 |
คุณสมบัติ 1 หมายถึง: สำหรับทุก $i$ มี $a_i \le p_i$
คุณสมบัติ 2 หมายถึง: $LCM(p_i) \le 10^6$ กล่าวคือ ค.ร.น. ของ $p_i$ ทั้งหมดไม่เกิน $10^6$
สำหรับทุกกรณีทดสอบ $T \le 5$ พลังโจมตีของอาวุธทั้งหมดไม่เกิน $10^6$ และ ค.ร.น. ของ $p_i$ ทั้งหมดไม่เกิน $10^{12}$
หมายเหตุ
ผลลัพธ์ระหว่างทางที่คุณใช้ในการคำนวณอาจมีค่ามาก โปรดระวังชนิดตัวแปรที่ใช้เก็บผลลัพธ์ระหว่างทาง