اكتشفت 小 D مؤخرًا لعبة صغيرة على الإنترنت. قواعد اللعبة كما يلي:
- الهدف هو قتل $n$ تنينًا بالترتيب من $1$ إلى $n$. لكل تنين قيمة صحة ابتدائية $a_i$، ولديه قدرة على التعافي: كلما استخدمها، تزداد صحته بمقدار $p_i$ في كل مرة، حتى تصبح غير سالبة. ولا يموت إلا بعد انتهاء الهجوم، وعندما تكون صحته مساوية للصفر تمامًا.
- عند بدء اللعبة، يمتلك اللاعب $m$ سيفًا ذات قوى هجوم معلومة. عند مواجهة كل تنين، يمكنه اختيار سيف واحد فقط. وبعد قتل التنين، يختفي هذا السيف، لكن اللاعب يحصل على سيف جديد مكافأةً له.
تجد 小 D هذه اللعبة مملة جدًا، لكن أسرع لاعب ينهيها يحصل على أهلية المشاركة في ION2018، لذلك قررت كتابة روبوت بسيط ليساعدها في إنهائها. يتبع الروبوت القواعد التالية:
- عند مواجهة كل تنين، يختار الروبوت من السيوف التي يمتلكها حاليًا السيف ذا أكبر قوة هجوم لا تتجاوز صحة التنين الابتدائية. وإذا لم يوجد سيف كهذا، فإنه يختار السيف ذا أقل قوة هجوم.
- عند مواجهة كل تنين، يستخدم الروبوت السيف المختار في الخطوة السابقة لمهاجمته عددًا ثابتًا من المرات هو $x$، مما يخفض صحة التنين بمقدار $x\times ATK$.
- بعد ذلك، يستخدم التنين قدرة التعافي مرارًا، ليستعيد $p_i$ من الصحة في كل مرة. فإذا كانت صحته صفرًا قبل استخدام قدرة التعافي، أو بعد إحدى مرات التعافي، يموت التنين ويجتاز اللاعب هذه المرحلة.
من الواضح إذن أن عدد هجمات الروبوت هو العامل الحاسم في إنهاء اللعبة بأسرع وقت. تعرف 小 D الآن جميع خصائص كل تنين، وتريد اختبارك: ما القيمة التي يجب ضبط عدد هجمات الروبوت $x$ عليها حتى يتمكن من إنهاء اللعبة بأقل عدد من الهجمات؟
وبالطبع، إذا تعذر إنهاء اللعبة مهما كانت القيمة المختارة، فأخرج -1.
الإدخال
اقرأ البيانات من الملف dragon.in.
يحتوي السطر الأول على عدد صحيح $T$، يمثل عدد حالات الاختبار.
تليه $T$ حالة اختبار، تتكون كل منها من 5 أسطر.
- يحتوي السطر الأول من كل حالة على عددين صحيحين $n$ و$m$، يمثلان عدد التنانين وعدد السيوف الابتدائية.
- يحتوي السطر التالي على $n$ عدد صحيح موجب، يمثل العدد رقم $i$ صحة التنين رقم $i$ الابتدائية $a_i$.
- يحتوي السطر التالي على $n$ عدد صحيح موجب، يمثل العدد رقم $i$ قدرة تعافي التنين رقم $i$، وهي $p_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$ مرة، تصبح صحته صفرًا تمامًا فيموت.
- يختفي السيف ذو قوة الهجوم $1$، ويُلتقط سيف ذو قوة هجوم $7$. تصبح قوى هجوم السيوف المملوكة $\{7,9,10\}$. صحة التنين الثاني تساوي $5$، لذلك يُختار السيف ذو قوة الهجوم $7$. يهاجم $59$ مرة، مسببًا $413$ نقطة ضرر، فتصبح صحة التنين $-408$. وبعد التعافي $68$ مرة، تصبح صحته صفرًا تمامًا فيموت.
- تصبح قوى هجوم السيوف المملوكة $\{3,9,10\}$. صحة التنين الثالث تساوي $7$، لذلك يُختار السيف ذو قوة الهجوم $3$. يهاجم $59$ مرة، مسببًا $177$ نقطة ضرر، فتصبح صحة التنين $-170$. وبعد التعافي $17$ مرة، تصبح صحته صفرًا تمامًا فيموت.
- لا توجد طريقة لإنهاء اللعبة بعدد هجمات أقل من $59$، لذا فالإجابة هي $59$.
حالة الاختبار الثانية:
- لا توجد طريقة تقتل التنين الأول والثاني معًا، ولذلك يتعذر إنهاء اللعبة ويُخرج
-1.
مثال 2
راجع الملفين dragon/dragon2.in وdragon/dragon2.ans في دليل المتسابق.
المهام الفرعية
| رقم حالة الاختبار | $n$ | $m$ | $p_i$ | $a_i$ | قوة الهجوم | قيود أخرى |
|---|---|---|---|---|---|---|
| 1 | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $=1$ | لا شيء |
| 2 | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $=1$ | لا شيء |
| 3 | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $\leq 10^5$ | لا شيء |
| 4 | $\leq 10^5$ | $=1$ | $=1$ | $\leq 10^5$ | $\leq 10^5$ | لا شيء |
| 5 | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | الخاصية 1، الخاصية 2 |
| 6 | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | الخاصية 1، الخاصية 2 |
| 7 | $\leq 10^3$ | $\leq 10^3$ | $\leq 10^5$ | $\leq 10^5$ | $\leq 10^5$ | الخاصية 1، الخاصية 2 |
| 8 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | الخاصية 1 |
| 9 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | الخاصية 1 |
| 10 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | الخاصية 1 |
| 11 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | الخاصية 1 |
| 12 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | الخاصية 1 |
| 13 | $=1$ | $=1$ | $\leq 10^8$ | $\leq 10^8$ | $\leq 10^6$ | الخاصية 1 |
| 14 | $=10^5$ | $=10^5$ | $=1$ | $\leq 10^8$ | $\leq 10^6$ | لا قيود خاصة |
| 15 | $=10^5$ | $=10^5$ | $=1$ | $\leq 10^8$ | $\leq 10^6$ | لا قيود خاصة |
| 16 | $\leq 10^5$ | $\leq 10^5$ | جميع قيم $p_i$ أولية | $\leq 10^{12}$ | $\leq 10^6$ | الخاصية 1 |
| 17 | $\leq 10^5$ | $\leq 10^5$ | جميع قيم $p_i$ أولية | $\leq 10^{12}$ | $\leq 10^6$ | الخاصية 1 |
| 18 | $\leq 10^5$ | $\leq 10^5$ | لا قيود خاصة | $\leq 10^{12}$ | $\leq 10^6$ | الخاصية 1 |
| 19 | $\leq 10^5$ | $\leq 10^5$ | لا قيود خاصة | $\leq 10^{12}$ | $\leq 10^6$ | الخاصية 1 |
| 20 | $\leq 10^5$ | $\leq 10^5$ | لا قيود خاصة | $\leq 10^{12}$ | $\leq 10^6$ | الخاصية 1 |
الخاصية 1 تعني: لكل $i$، فإن $a_i\leq p_i$.
الخاصية 2 تعني: $\operatorname{LCM}(p_i)\leq 10^6$، أي أن المضاعف المشترك الأصغر لجميع قيم $p_i$ لا يتجاوز $10^6$.
لجميع حالات الاختبار: $T\leq 5$، وقوة هجوم جميع الأسلحة لا تتجاوز $10^6$، والمضاعف المشترك الأصغر لجميع قيم $p_i$ لا يتجاوز $10^{12}$.
ملاحظة
قد تكون النتائج الوسيطة التي تستخدمها كبيرة جدًا. انتبه إلى نوع المتغيرات التي تخزن فيها هذه النتائج.