A. Оройн хоолонд юу идэх вэ?

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

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

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

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

Уотерланд гэх нэгэн нийтэд танигдаагүй, үзэсгэлэнт газарт өхөөрдөм Валерие аварга загас амьдардаг. Бүхий л аварга загасын адилаар тэр хэд хэдэн эгнээ шүдтэй бөгөөд зөвхөн хэлтэг загасаар хооллодог. Бусдаас ялгарах Валериегийн нэг онцлог бол тэр нэг хэлтэг идэхдээ зөвхөн нэг эгнээ шүдээрээ л иддэг ба бусад шүд нь "амарч" байдаг.

Тэрээр олон жилийн турш тэнгист хэлтэг загас ангуучилжээ. Гэвч нэгэн азгүй явдал тохиолдол болж түүний шүд өвдөж эхэлсэн ба тэр нутгийнхаа шүдний эмч Ашот хавчид үзүүлэв. Ашот мэргэжлийн өндөр түвшин үйлчилж нэн даруй Валериег шүдний өвчнөөс нь ангижруулав. Түүнчлэн тэр Валериегийн шүд хорхойтолтын (Ашот хожим нь Кап гэж нэрлэсэн шалтгааныг тодорхойлжээ.

Энэ нь Валериегийн хэт олон хэлтэг идсэнээс болсон байжээ. Валериег цаашид тохиолдох шүдний өвчнөөс зайлсхийхэд туслаарай. Ашот Валериегийн бүх шүдний хувьд тэсч үлдэх чадварыг тогтоожээ. Шүдний тэсч үлдэх чадвар нь Валериегийн энэхүү шүдээрээ идэж чадах нийт хэлтэгний тоотой тэнцүү байна. Валериег хэлтэг идэх бүрд уг хэлтэгийг идэхэд оролцож буй бүх шүдний тэсч үлдэх чадвар нэгээр хорогдоно. Аль нэг шүдний тэсч үлдэх чадвар сөрөг утгатай болох бүрд тэр шүдний эмчид дахин үзүүлэх шаардлагатай болно.

Валерие түүнийг хүлээж буй хэсэг хэлтэг байгаа гэртээ гунигтайхан буцаж ирлээ. Мэдээж тэр өөрийн дуртай хоолондоо үгүй гэж чадахгүй ч бас шүдний эмчид очих хүсэл байсангүй. Тиймээс тэр аль ч шүдний тэсч үлдэх чадварыг сөрөг болгохгүйгээр хамгийн их хэмжээний хэлтэг идэхээр шийджээ.

Валерие математикт сайн биш учраас тэр танаас оройн хоолондоо идэж болох хэлтэгний боломжит хамгийн их хэмжээг олж өгөхийг хүсч байна.

Бид танд Валерие нэг хэлтэг идэхдээ яг нэг эгнээ шүд оролцуулж иддэг ба энэ эгнээнд байгаа бүх шүдний чадвар $1$-ээр хорогдох болохыг сануулъя.

Оролт

Эхний мөр нь Валериегийн нийт шүдний тоо, шүдний эгнээний тоо болон оройн хоолондоо идэх хэлтэгний хэмжээг харуулах $n$, $m$, $k$ ($1 ≤ m ≤ n ≤ 1000, 0 ≤ k ≤ 10^{6}$) гурван бүхэл тоог агуулна. Дараагийн $n$ мөрүүд нь тус бүрдээ тухайн шүдэнд харгалзах эгнээний дугаар, тухайн шүдний тэсч үлдэх чадварыг харуулах $r$ ($1 ≤ r ≤ m$) ба $c$ ($0 ≤ c ≤ 10^{6}$) хоёр бүхэл тоог агуулна.

Эгнээ бүр эерэг тоон утга бүхий шүдтэй гэж үзнэ.

Гаралт

Валериегийн оройн хоолондоо идэж болох хэлтэгний хамгийн их тоог хэвлээрэй.

Орчуулсан: Солонго

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

Оролт
4 3 18
2 3
1 2
3 6
2 3
Гаралт
11
Оролт
2 2 13
1 13
2 12
Гаралт
13
Сэтгэгдлүүдийг ачааллаж байна...