Bir do'konda mahsulot narxi \(n\) va u sotib olinayotgan miqdor \(m\) berilgan. Do'kon quyidagi qoida bo'yicha chegirma beradi:

• Agar xaridning umumiy summasi \((n \times m)\) \(500 000\) so'mdan katta yoki teng bo'lsa, xaridorga \(15\)% chegirma beriladi.
• Aks holda, chegirma berilmaydi.

Xaridorning narxi va miqdorini bilib, u to'lashi kerak bo'lgan yakuniy summani hisoblab bering.

Yagona qatorda ikkita butun son beriladi: \(n\) va \(m\) (bo'sh joy bilan ajratilgan).

• \(1 \le n \le 10^6\)
• \(1 \le m \le 1000\)

Yakuniy summani \(10^{-2}\) xona aniqlikda chiqaring.

Toshkent shahridagi mashhur Chorsu bozori oldidagi maydon to'g'ri to'rtburchak shaklida bo'lib, uning o'lchamlari \(n \times m\) metrni tashkil etadi. Bayram munosabati bilan ushbu maydonni granit plitalar bilan qoplash rejalashtirilmoqda. Qo'llaniladigan har bir plita kvadrat shaklida bo'lib, tomoni a metrga teng.

Butun maydonni to'liq qoplash uchun eng kam miqdorda nechta plita talab qilinishini aniqlang.

Shuni hisobga olish kerak:

• Plitalar bilan maydondan biroz kattaroq yuza qoplansa ham bo'ladi, biroq maydonning har bir nuqtasi albatta yopilgan bo'lishi shart;
• Plitalarni bo'laklarga ajratish yoki kesish taqiqlanadi — faqat butun holida qo'yiladi;
• Har bir plitaning qirralari maydon tomonlariga nisbatan parallel joylashtirilishi kerak.

Yagona qatorda uchta musbat butun son beriladi — \(n\), \(m\) va \(a\) (\(1 ≤ n, m, a ≤ 10^9\)), bular navbati bilan maydonning uzunligi, kengligi va plitaning tomoni uzunligini bildiradi.

Maydonni to'liq qoplash uchun zarur bo'lgan minimal plitalar sonini toping.

Kirito (asl ismi Kirigaya Kazuto) o'yinining bir bosqichida qolib ketgan. Keyingi bosqichga o'tish uchun u ushbu bosqichda yashaydigan barcha \(n\) ta ajdarni yengishi kerak.

Kirito va har bir ajdarning kuchi butun son bilan ifodalanadi. Ikki raqib o'rtasidagi jangda kuchi kattaroq bo'lgani g'alaba qozonadi; agar kuchlari teng bo'lsa, ikkinchi bo'lib jang qilgan g'alaba qozonadi (ya'ni Kirito). Agar Kirito eng zaif ajdardan boshlab jang qilsa, u barcha ajdalarni yengib, keyingi bosqichga o'ta oladi.

Boshlang'ich holatda Kiritoning kuchi \(s\) ga teng. Agar Kirito \(i-\)ajdarni yengsa, uning kuchi \(y_i\) songa ortadi (bu ajdarni yengish evaziga olinadigan tajriba ochkolari). Kirito ajdarlar bilan jang qilish tartibini o'zi tanlashi mumkin.

Kirito barcha \(n\) ta ajdarni yengib, keyingi bosqichga o'ta oladimi yoki yo'qligini aniqlang.

Birinchi qatorda ikkita butun son \(n\) va \(s\) (\(1 \le n \le 10^5\), \(1 \le s \le 10^4\)) — ajdarlar soni va Kiritoning boshlang'ich kuchi beriladi.

Keyingi \(n\) ta qatorning har birida ikkita butun son \(x_i\) va \(y_i\) (\(1 \le x_i \le 10^4\), \(0 \le y_i \le 10^4\)) beriladi — bu \(i-\)ajdarning kuchi va uni yengganda olinadigan tajriba ochkolari sonini bildiradi.

Agar Kirito barcha ajdarlarni yengib, keyingi bosqichga o'ta olsa — \(YES\) so'zini, aks holda — \(NO\) so'zini chiqaring (qo'shtirnoqsiz).

De_mirage xaritasining "mid" hududida \(n\) ta dushman ko'rish chizig'i (sightline) bor — bular dushman sizni ko'ra oladigan to'g'ri chiziq segmentlari (masalan, "Palace" dan "Mid"gacha, yoki "Window" orqali).

Sizda oldindan tayyorlangan (lineup) \(m\) ta tutun granatasi otish nuqtasi bor — har biri aniq \((p_x, p_y)\) koordinataga tushadi va radiusi \(R\) bo'lgan doira hosil qiladi.

Bir sightline to'silgan hisoblanadi, agar tutun doirasi shu segment bilan kamida bitta umumiy nuqtaga ega bo'lsa (ya'ni, nuqtadan segmentgacha bo'lgan eng qisqa masofa \(\le R\)).

Sizga qaysi otish nuqtasini tanlash eng ko'p sightline'ni to'sishini aniqlash kerak.

CS2'da "mid" hududidagi tutun granatasi lineup nuqtasi

Birinchi qatorda uchta butun son \(n\), \(m\) va \(R\) (\(1 \le n, m \le 2000\); \(1 \le R \le 10000\)) — mos ravishda dushman ko'rish chiziqlari (sightlines) soni, tutun tashlash nuqtalari soni va tutun doirasining radiusi.

Keyingi \(n\) ta qatorning har birida to'rtta butun son \(x_1, y_1, x_2, y_2\) (\(-10^4 \le x_1, y_1, x_2, y_2 \le 10^4\)) — har bir dushman ko'rish chizig'i segmentining boshlang'ich va oxirgi nuqtalari koordinatalari beriladi.

Keyingi \(m\) ta qatorning har birida ikkita butun son \(p_x, p_y\) (\(-10^4 \le p_x, p_y \le 10^4\)) — har bir tutun granatasi tushadigan nuqtaning \((x, y)\) koordinatalari beriladi.

Eng ko'p sightline'ni to'suvchi otish nuqtasining raqamini (\(1-\)indeksli) va u to'sadigan sightline'lar sonini chiqaring (bo'sh joy bilan ajratib). Agar bir nechta nuqta bir xil sondagi sightline'ni to'ssa, eng kichik raqamlisini chiqaring.

Xarita \(V\) ta xona (tugun) va ular orasidagi \(E\) ta ikki tomonlama koridor (qirra) ko'rinishida berilgan. Terroristlar \(S-\)xonada (\(T-\)spawn) boshlanadi va \(T-\)xonaga (bombasite) yetib borishni xohlaydi.

Sizning jamoangiz istalgan xonada (\(S\) va \(T\) dan tashqari — o'z spawningizni yoki bombasitening o'zini "to'sib" bo'lmaydi) \(1\) ta o'yinchi qo'yib, o'sha xonani to'liq yopib qo'yishi mumkin: agar terroristlar shu xona orqali o'tishga uringanida, ular albatta ko'rinadi va to'xtatiladi — ya'ni to'silgan xona orqali o'tish umuman mumkin emas.

Koridorlarning o'zi (ikki xona orasidagi yo'l) to'sib bo'lmaydi — faqat xonalarni. Bitta xonaga nechta odam qo'ysangiz ham, u faqat bitta marta "to'silgan" hisoblanadi (qo'shimcha odam foyda bermaydi).

Sizga: terroristlar \(S\) dan \(T\) ga hech qanday yo'l bilan (to'silmagan xonalar orqaligina) yeta olmasligi uchun, minimal nechta xonani to'sish kerakligini toping.

Agar \(S\) va \(T\) orasida to'g'ridan-to'g'ri koridor mavjud bo'lsa (ya'ni ular bevosita qo'shni bo'lsa), ularni hech qanday xona sonini to'sib ajratib bo'lmaydi (chunki bu yo'lda to'siladigan xona umuman yo'q) — bunday holatda \(-1\) chiqaring.

Birinchi qatorda \(V, E, S, T\) (\(2 \le V \le 500\); \(1 \le E \le 2000\); \(1 \le S, T \le V\); \(S \neq T\)) — mos ravishda xonalar soni, koridorlar soni, \(T-\)spawn xonasi va bombasite xonasi.

Keyingi \(E\) ta qatorning har birida: \(u, v\) (\(1 \le u, v \le V\); \(u \neq v\), bir xil juftlik bir necha marta takrorlanishi mumkin) — \(u\) va \(v\) xonalari orasida koridor borligini bildiradi.

Terroristlarni \(S\) dan \(T\) ga yetib borishini butunlay to'sish uchun kerak bo'ladigan minimal xonalar sonini chiqaring. Agar \(S\) va \(T\) bevosita qo'shni bo'lsa \(-1\) chiqaring.

Naruto Uzumaki navbatdagi mashqda Kage Bunshin no Jutsu yordamida \(n\) ta soya klon yaratdi. \(i-\)klonning kuch darajasi \(b_i\). Xuddi shu payt uning oldiga \(m\) ta dushman ninja chiqib keldi — ularning kuch darajalari \(e_1, e_2, …, e_m\).

Bitta klon bitta dushman ninjani mag'lub eta oladi, agar uning kuchi dushmannikidan kam bo'lmasa (\(b_i ≥ e_j\)). Har bir klon jangdan so'ng chakrasi tugab yo'qoladi, shu sabab faqat bitta jangda qatnasha oladi; har bir dushman ham faqat bitta klon tomonidan mag'lub etilishi mumkin — ikkita klon birlashib bitta dushmanga hujum qila olmaydi.

Naruto klonlarini shunday taqsimlaydiki, mag'lub etilgan dushmanlar soni maksimal bo'lsin. Ushbu maksimal sonni toping.

Birinchi qatorda ikkita butun son \(n\) va \(m\) (\(1 ≤ n, m ≤ 2 \times 10^5\)) beriladi.

Ikkinchi qatorda \(n\) ta butun son \(b_1, b_2, …, b_n\) (\(1 ≤ b_i ≤ 10^9\)) — klonlarning kuch darajalari.

Uchinchi qatorda \(m\) ta butun son \(e_1, e_2, …, e_m\) (\(1 ≤ e_j ≤ 10^9\)) — dushman ninjalarning kuch darajalari.

Bitta butun son Naruto mag'lub eta oladigan dushmanlarning maksimal sonini chop eting.

Konoha ninjalari orasidagi ustoz–shogird munosabati \(n\) tugunli daraxt hosil qiladi: tugun \(1-\)Hokage (ildiz), qolgan har bir ninja \(i\) (\(2 ≤ i ≤ n\)) uchun uning bevosita ustozi \(p_i \) beriladi. Har bir ninja \(i\) ning jangovar kuchi \(w_i \) bilan berilgan.

Besh Kage anjumanini himoya qilish uchun maxsus otryad tuzilmoqda. Ammo Konoha tadqiqotchilari xavfli hodisani aniqladi: agar otryadga daraxt bo'yicha masofasi \(2\) yoki undan kam bo'lgan ikkita ninja kiritilsa, ularning chakralari rezonansga kirib, jang paytida ikkalasi ham ishlatib bo'lmay qoladi. Shu sababli otryadga kiritilgan istalgan ikki ninja orasidagi daraxt bo'yicha masofa (ular orasidagi eng qisqa yo'ldagi qirralar soni) kamida \(3\) bo'lishi shart.

Hokage otryadga kirgan ninjalarning jangovar kuchlari yig'indisini maksimal qilmoqchi. Ushbu maksimal yig'indini toping.

Birinchi qatorda bitta butun son \(n\) beriladi.

Ikkinchi qatorda \(n-1\) ta butun son \(p_2, p_3, …, p_n\) beriladi — \(p_i \) ninja \(i\) ning bevosita ustozi (\(1 ≤ p_i < i\)). Bu massiv har doim to'g'ri daraxt hosil qilishini kafolatlaydi.

Uchinchi qatorda \(n\) ta butun son \(w_1, w_2, …, w_n\) — ninjalarning jangovar kuchlari.

\(2 ≤ n ≤ 2 \times 10^5 \)
\(1 ≤ p_i < i\)
\(1 ≤ w_i ≤ 10^9\)

Bitta butun son - otryadga kiritilishi mumkin bo'lgan ninjalarning jangovar kuchi yig'indisining maksimal qiymatini chop eting.

PUBG Mobile'ning yangi mavsumida O'rgimchak-odam bilan hamkorlik e'lon qilindi: endi o'yinchi o'z ip otuvchisi (web-shooter) yordamida binolar orasida tezda sakrashi mumkin. 

Erangel orolida n ta bino joylashgan, ularning koordinatalari tekislikda berilgan. O'yinchi hozir 1-binoda turibdi va faqat binolar orasida (erkin yugurmasdan, faqat bino-bino)
harakat qila oladi.

Ikkita bino orasidagi Yevklid masofa d bo'lsin:
- Agar \(d ≤ R\) bo'lsa (R — ipning maksimal uzunligi), o'yinchi ip otib sakrashi mumkin — bu safar tezligi \(v_w \)(vaqt = \(d / v_w\)).
- Istalgan ikkita bino orasida (masofadan qat'i nazar) piyoda ham yurish mumkin — tezligi \(v_p (v_p < v_w)\), vaqt =\( d / v_p\).

O'yinchi har safar ikki variantdan birini tanlaydi (agar \(d ≤ R\) bo'lsa, tezroq bo'lgani uchun odatda ip afzal, lekin bu shart emas — masala shuni hisoblab topishi kerak).

O'yin davomida xavfsiz zona asta-sekin torayib, T soniyadan so'ng markazi (cx, cy) da, radiusi r bo'lgan yakuniy doiraga aylanadi va shu yerda to'xtaydi.
Omon qolish uchun o'yinchi T soniyagacha markazigacha masofasi r dan oshmaydigan (ya'ni yakuniy doira ichidagi) biror binoga yetib borishi kerak.

O'yinchi eng qisqa vaqtda yakuniy zonaga yetib bora oladimi? Agar ha bo'lsa, buning uchun zarur bo'lgan minimal vaqtni toping.

- 1-qator: \(n (2 ≤ n ≤ 2000)\)
- 2-qator: \(v_p, v_w, R\) — piyoda tezligi, ip bilan sakrash tezligi, ip radiusi (\(1 \le v_p < v_w \le 10^3\), \(1 \le R \le 3 \times 10^5\))
- 3-qator: cx, cy, r, T — yakuniy zonaning markazi, radiusi va qolgan vaqt (\(-10^5 \le cx, cy \le 10^5\); \(0 \le r \le 3 \times 10^5\); \(1 ≤ T ≤ 10^9\))
- Keyingi n qatorning har birida \(x_i, y_i\) — i-binoning koordinatalari \((-100000 ≤ x_i, y_i ≤ 100000)\). 1-bino — o'yinchining boshlang'ich joyi.

Agar o'yinchi T soniya ichida yakuniy zonaga yetib bora olsa, minimal vaqtni \(10^{-6}\) xona aniqlikda chop eting. Aks holda — "NO" so'zini chiqaring.