E. ГРИП-ийн түүх

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Нэг удаа Квэрти онгоцтойгоо өөр нэгэн онгоцтой мөргөлджээ. Үр дүнд нь тэр хоёрын авч явсан тээш сансараар нэг таржээ. Квэрти Тарсан тээшүүдээс аль болох олныг цуглуулж дараа нь зарахыг хүсчээ.

Асуудал нь $2$ онгоц их олон шинэ татах хүчний ГРИП-ийг зарахаар авч явжээ. ГРИП гэдэг нь сансарын хөлөгт суурьлуулдаг бараа тээшийг барьж аван каргогийн хэсэгрүү оруулдаг багаж юм.

Осолдсон онгоцнууд нийт $n$ ГРИП алдсан байна: $i$-дэх ГРИП нь $(x_{i}, y_{i})$ кординатад байрлана. ГРИП бүр $2$ үзүүлэлттэй -- $p_{i}$ хүчийг нь илэрхийлнэ, $r_{i}$ нь ачаа тээшийг авч чадах орчны радиус. Өөрөөр хэлбэл тухайн ГРИП $p_{i}$-ээс илүүгүи жинтэй $r_{i}$-аас холгүй байгаа ачааг авч чадна гэсэн үг юм. ГРИП нь өөрөө мөн ачаа бөгөөд $m_{i}$ жинтэй.

Квэртигийн онгоц $(x, y)$ цэг дээр байлаж байгаа ба түүнд хуучны нэгэн соронзон ГРИП байгаа аж. Түүний чадал $p$ ба радиус нь $r$. Онгоцонд өөр ГРИП үлдээгүй аж.

Квэртигийн цуглуулж чадах хамгийн их ГРИП-ийн тоог ол. Тэрээр барьж авсан ГРИП-ээ мөн онгоцондоо суурьлуулж болно. Аль ч хоромд онгоц зөвхөн нэг ГРИП ашиглана. Бид ГРИП-ээр барисан байгаа зүйлсээс бусдийг хөдөлгөөнгүй байгаа гэж үзнэ. Тэгэхлээр ГРИП ямар нэгэн зүйлийг авч байхад онгоц хөдлөхгүй юм. Мөн онгоц бүх ГРИП-ийг хадгалах хангалттай олон өрөөтэй гэж үзнэ. Квэрти өөрт байгаа ГРИП-үүдээ хэдэн ч удаа алийг нь ч ашигаж болно.

Оролт

Эхнии мөрөнд хөлгийн байрлал, анхны соронзон ГРИП-ийн үзүүлэлтүүд болон тарсан ГРИП-ийн тоог илэрхийлэх $x$, $y$, $p$, $r$, $n$ ($ - 10^{9} ≤ x, y ≤ 10^{9}$, $1 ≤ p, r ≤ 10^{9}$, $1 ≤ n ≤ 250000$) гэсэн $5$ бүхэл тоо байна.

Дараагийн $n$ мөр бүрт ГРИП-үүдийг тодорхойлсон тоонууд байна: $i$-дэх мөрөнд $i$ дэх ГРИП-ийн координат масс ба үзүүлэлтийг илэрхийлсэн $x_{i}$, $y_{i}$, $m_{i}$, $p_{i}$, $r_{i}$ ($ - 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}$, $1 ≤ m_{i}, p_{i}, r_{i} ≤ 10^{9}$) таван бүхэл тоо байна.

Бүх ГРИП-үүд ялгаатай байрлалтай ба аль нь ч Квэртигийн онгоцтой давхцахгүй.

Гаралт

Анхны соронзон ГРИП-ийг тооцохгүйгээр хэдэн ГРИП-ийг Квэрти авч чадах вэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
0 0 5 10 5
5 4 7 11 5
-7 1 4 7 8
0 2 13 5 6
2 -3 9 3 4
13 5 1 9 9
Гаралт
3

Тэмдэглэл

Эхний жишээнд эхлээд 2-р ГРИП-ийг авч түүгээрээ 1-р ГРИП-ийг авна, тэгээд 1-р ГРИП-ээр 4-р ГРИП-ийг авна. 3-р ГРИП хэт хүнд тул авч чадахгүй ба 5-р ГРИП хэт хол тул авч чадахгүй.

Сэтгэгдлүүдийг ачааллаж байна...