F. Цас худалдаалагчид

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

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

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

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

Берландад шинэ жилийг $n$ өдрийн турш тэмдэглэдэг байв. Зөвхөн энэ жилийн өвөл цас багатай байгаа учраас шинэ жил зохион байгуулагчид нь хиймэл цас худалдаалах болжээ. Берландад $m$ ширхэг цас зардаг байгууллага бий. Өдөр бүр $i$-р байгууллага $w_{i}$ метр куб цас үйлдвэрлэдэг. Дараа өдөр нь цас хайлах бөгөөд иймд байгууллага нь дахин $w_{i}$ метр куб цас үйлдвэрлэдэг байв. Шинэ жилийн үеэр олон хямдралууд зарлагддаг бөгөөд иймд цасны үнэ өдөр бүр буурч байжээ. Түүнчлэн эхний өдөр $i$-р байгууллагын үйлдвэрлэсэн бүх цасны нийт үнэ нь $c_{i}$ боурле-тэй тэнцүү байх юм. Өдөр болгон уг нийт үнэ нь $a_{i}$ боурле-ээр багасах буюу өөрөөр хэлбэл 2-дахь өдөр нийт үнэ нь $c_{i} - a_{i}$-тай тэнцүү болно, 3-дахь өдөр $c_{i} - 2a_{i}$-тай тэнцүү болно гэх мэтчилэн үргэлжлэх ажээ. Мөн ямар нэгэн байгууллагын хувьд тухайн байгууллагын үйлдвэрлэсэн цасны нийт үнэ нь сөрөг тоо болон 0-тэй тэнцүү биш байна гэдэг нь мэдэгдэж байв. Та өдөр болгон яг $W$ метр куб цас худалдан авч байхаар цас худалдан авах хэрэгтэй болжээ. Түүнчлэн ямар нэгэн байгууллагаас тухайн байгууллагын үйлдвэрлэсэн бүх цасыг худалдан авах албагүй. Хэрэв та $i$-р байгууллагаас цасны үнэ нь $s_{i}$-тэй тэнцүү байх өдөр $n_{i}$ ($0 ≤ n_{i} ≤ w_{i}$, $n_{i}$ тоо нь бүхэл тоо байх албагүй!) метр куб цас худалдан авбал та нийт боурле төлөх юм. Нэг өдрийн турш үйлчлүүлэгч хэд хэдэн байгууллагаас цас худалдан авч болох бөгөөд ялгаатай өдрүүдэд өөр өөр байгууллагуудаас цас худалдан авч болно. Та аль болох боломжит бага хэмжээний мөнгө зарцуулан худалдан авалт хийх ёстой болжээ. Мөн байгууллагуудын үйлдвэрлэж буй цас нь хангалттай их байна гэж үзнэ үү.

Оролт

Эхний мөрөнд бүхэл тоонууд $n$, $m$ болон $W$ ($1 ≤ n ≤ 100$, $1 ≤ m ≤ 500000$, $1 ≤ W ≤ 10^{9}$)-ууд өгөгдөх ба эдгээр нь шинэ жил үргэлжлэх өдрийн тоо, байгууллагын тоо болон $n$ өдрийн турш өдөр болгон худалдан авах ёстой цасны хэмжээг илэрхийлнэ. 2-дахь мөрөнд $m$ ширхэг бүхэл тоонууд $w_{i}$-ууд өгөгдөнө. 3-дахь мөрөнд $m$ ширхэг бүхэл тоонууд $c_{i}$-ууд өгөгдөнө. 4-дэх мөрөнд $m$ ширхэг бүхэл тоонууд $a_{i}$-ууд өгөгдөнө. Бүх тоонууд нь заавал эерэг тоо байх бөгөөд $10^{9}$-өөс хэтрэхгүй байна. Түүнчлэн бүх $i$-ын хувьд $c_{i} - (n - 1)a_{i} > 0$ тэнцэтгэл биш биелж байна.

Гаралт

Бодлогын хариулт болох ганц бүхэл тоог хэвлэнэ үү. Хариултыг таслалын ард байрлах оронтой нь хэвлэх бөгөөд хариулт нь тэгээр эхлэхгүй мөн "e" агуулаагүй байна. Түүнчлэн хариулт нь бүхэл тоо байсан ч таслалын ард байрлах оронтой нь цуг хэвлэхийг анхаарна уу. Таны хариулт болон зөв хариултын зөрүү нь $10^{ - 9}$-өөс ихгүй байх ёстой.

Орчуулсан: Баатархүү

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

Оролт
2 3 10
4 4 4
5 5 8
1 2 5
Гаралт
22.000000000000000
Оролт
100 2 1000000000
999999998 999999999
1000000000 1000000000
1 1
Гаралт
99999995149.999995249999991
Сэтгэгдлүүдийг ачааллаж байна...