小 D גילתה לאחרונה משחק קטן באינטרנט. כללי המשחק הם:
- מטרת המשחק היא להרוג $n$ דרקונים לפי הסדר $1\sim n$. לכל דרקון ערך חיים התחלתי $a_i$ ויכולת התאוששות. כאשר הוא משתמש בה, ערך חייו גדל ב־$p_i$ בכל פעם, עד שהוא אי־שלילי. הדרקון מת רק לאחר שההתקפה הסתיימה וכאשר ערך חייו הוא בדיוק $0$.
- בתחילת המשחק יש לשחקן $m$ חרבות שעוצמות ההתקפה שלהן ידועות. בכל מפגש עם דרקון אפשר לבחור חרב אחת בלבד. לאחר הריגת הדרקון החרב נעלמת, אך השחקן מקבל חרב חדשה כפרס.
小 D חושבת שהמשחק משעמם מאוד, אבל השחקן שישלים אותו במהירות הרבה ביותר יזכה בזכות להשתתף ב־ION2018. לכן היא החליטה לכתוב רובוט טיפש שיעזור לה להשלים אותו. הרובוט שלה פועל לפי הכללים הבאים:
- בכל מפגש עם דרקון הוא בוחר, מבין החרבות שבידיו שעוצמתן אינה עולה על ערך החיים ההתחלתי של הדרקון, את החרב בעלת עוצמת ההתקפה המרבית. אם אין חרב כזאת, הוא בוחר את החרב בעלת העוצמה המזערית.
- מול כל דרקון הוא משתמש בחרב שבחר כדי לתקוף בדיוק $x$ פעמים, ומפחית את ערך חיי הדרקון ב־$x\times ATK$.
- לאחר מכן הדרקון משתמש שוב ושוב ביכולת ההתאוששות שלו, ומחזיר $p_i$ חיים בכל פעם. אם ערך חייו הוא $0$ לפני ההתאוששות או לאחר אחת מפעולות ההתאוששות, הוא מת והשחקן עובר את השלב.
ברור אפוא שמספר ההתקפות של הרובוט הוא המפתח להשלמת המשחק במהירות הרבה ביותר. 小 D כבר יודעת את כל תכונות הדרקונים ורוצה לבחון אתכם: לאיזה ערך יש לקבוע את מספר ההתקפות $x$ כדי להשלים את המשחק במספר ההתקפות המזערי?
אם אי אפשר להשלים את המשחק באף ערך של $x$, הדפיסו -1.
קלט
יש לקרוא את הנתונים מהקובץ dragon.in.
השורה הראשונה מכילה מספר שלם $T$, המציין את מספר מקרי הבדיקה.
לאחר מכן באים $T$ מקרים, שכל אחד מהם מכיל חמש שורות:
- השורה הראשונה בכל מקרה מכילה שני מספרים שלמים $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\}$, ולדרקון הראשון יש $3$ חיים. לכן נבחרת החרב שעוצמתה $1$. לאחר $59$ התקפות נגרם נזק של $59$ וערך חיי הדרקון הוא $-56$. לאחר $14$ התאוששויות ערך חייו הוא בדיוק $0$, והוא מת.
- החרב שעוצמתה $1$ נעלמת, ומתקבלת חרב שעוצמתה $7$. כעת עוצמות החרבות הן $\{7,9,10\}$, ולדרקון השני יש $5$ חיים. לכן נבחרת החרב שעוצמתה $7$. לאחר $59$ התקפות נגרם נזק של $413$ וערך חיי הדרקון הוא $-408$. לאחר $68$ התאוששויות ערך חייו הוא בדיוק $0$, והוא מת.
- כעת עוצמות החרבות הן $\{3,9,10\}$, ולדרקון השלישי יש $7$ חיים. לכן נבחרת החרב שעוצמתה $3$. לאחר $59$ התקפות נגרם נזק של $177$ וערך חיי הדרקון הוא $-170$. לאחר $17$ התאוששויות ערך חייו הוא בדיוק $0$, והוא מת.
- אין דרך להשלים את המשחק בפחות מ־$59$ התקפות, ולכן התשובה היא $59$.
המקרה השני:
- אין דרך להרוג גם את הדרקון הראשון וגם את השני, ולכן אי אפשר להשלים את המשחק והפלט הוא
-1.
דוגמה 2
ראו את הקבצים dragon/dragon2.in ו־dragon/dragon2.ans בתיקיית המתחרה.
תתי־משימות
| מספר מקרה הבדיקה | $n$ | $m$ | $p_i$ | $a_i$ | עוצמת ההתקפה | מגבלות נוספות |
|---|---|---|---|---|---|---|
| $1$ | $\leq10^5$ | $=1$ | $=1$ | $\leq10^5$ | $=1$ | אין |
| $2$ | $\leq10^5$ | $=1$ | $=1$ | $\leq10^5$ | $=1$ | אין |
| $3$ | $\leq10^5$ | $=1$ | $=1$ | $\leq10^5$ | $\leq10^5$ | אין |
| $4$ | $\leq10^5$ | $=1$ | $=1$ | $\leq10^5$ | $\leq10^5$ | אין |
| $5$ | $\leq10^3$ | $\leq10^3$ | $\leq10^5$ | $\leq10^5$ | $\leq10^5$ | תכונות 1 ו־2 |
| $6$ | $\leq10^3$ | $\leq10^3$ | $\leq10^5$ | $\leq10^5$ | $\leq10^5$ | תכונות 1 ו־2 |
| $7$ | $\leq10^3$ | $\leq10^3$ | $\leq10^5$ | $\leq10^5$ | $\leq10^5$ | תכונות 1 ו־2 |
| $8$ | $=1$ | $=1$ | $\leq10^8$ | $\leq10^8$ | $\leq10^6$ | תכונה 1 |
| $9$ | $=1$ | $=1$ | $\leq10^8$ | $\leq10^8$ | $\leq10^6$ | תכונה 1 |
| $10$ | $=1$ | $=1$ | $\leq10^8$ | $\leq10^8$ | $\leq10^6$ | תכונה 1 |
| $11$ | $=1$ | $=1$ | $\leq10^8$ | $\leq10^8$ | $\leq10^6$ | תכונה 1 |
| $12$ | $=1$ | $=1$ | $\leq10^8$ | $\leq10^8$ | $\leq10^6$ | תכונה 1 |
| $13$ | $=1$ | $=1$ | $\leq10^8$ | $\leq10^8$ | $\leq10^6$ | תכונה 1 |
| $14$ | $=10^5$ | $=10^5$ | $=1$ | $\leq10^8$ | $\leq10^6$ | אין מגבלות מיוחדות |
| $15$ | $=10^5$ | $=10^5$ | $=1$ | $\leq10^8$ | $\leq10^6$ | אין מגבלות מיוחדות |
| $16$ | $\leq10^5$ | $\leq10^5$ | כל ערכי $p_i$ ראשוניים | $\leq10^{12}$ | $\leq10^6$ | תכונה 1 |
| $17$ | $\leq10^5$ | $\leq10^5$ | כל ערכי $p_i$ ראשוניים | $\leq10^{12}$ | $\leq10^6$ | תכונה 1 |
| $18$ | $\leq10^5$ | $\leq10^5$ | אין מגבלות מיוחדות | $\leq10^{12}$ | $\leq10^6$ | תכונה 1 |
| $19$ | $\leq10^5$ | $\leq10^5$ | אין מגבלות מיוחדות | $\leq10^{12}$ | $\leq10^6$ | תכונה 1 |
| $20$ | $\leq10^5$ | $\leq10^5$ | אין מגבלות מיוחדות | $\leq10^{12}$ | $\leq10^6$ | תכונה 1 |
תכונה 1 פירושה שלכל $i$ מתקיים $a_i\leq p_i$.
תכונה 2 פירושה $LCM(p_i)\leq10^6$, כלומר הכפולה המשותפת המזערית של כל ערכי $p_i$ אינה עולה על $10^6$.
לכל מקרי הבדיקה מתקיים $T\leq5$, עוצמת ההתקפה של כל כלי נשק אינה עולה על $10^6$, והכפולה המשותפת המזערית של כל ערכי $p_i$ אינה עולה על $10^{12}$.
רמז
תוצאות הביניים עשויות להיות גדולות מאוד. שימו לב לטיפוסי המשתנים המשמשים לשמירתן.