C. Оюутнуудын өшөө авалт

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

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

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

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

Оюутны амьдрал олон хүндрэл агуулсан байдаг. Берландын хэсэг их сургуулийн оюутнууд үүнийг маш сайн мэддэг. 2 жил сурсны дараа тэд сургуулийн зарим тэнхимийн захиралтай муу харилцаатай болсон байв. Үнэндээ тэр сонин үйлдэл их хийдэг. Жишээ нь эхлээд байн байн групп болгон хуваах ба автоматаар хичээлдээ тэнцэхийг хориглох гэх мэт бусад олон онцгүй шалгуур тавьдаг. Тиймээс эцэст нь оюутнууд түүнийг ийм хэвээр нь байлгаад байж болохгүй хэмээн шийджээ.

Оюутнууд маш их гомдол гаргасан ба дараагийн их сургуулийн захирлуудын хурал дээр муухай ааштай захирлын тухай $n$ ширхэг тушаалыг авч хэлэлцэх ба тэдгээрийн яг $p$-г нь батална гэдгийг олж мэджээ. Тушаал бүрийн хувьд 2 утга өгөгдөх юм: хэрэв муухай ааштай захирал тушаалыг биелүүлбэл түүний бууралтах үсний тоо $a_{i}$ болон хэрэв тушаалыг биелүүлэхгүй бол захирлуудын уурлах дургүйцэл $b_{i}$ өгөгдөнө. Оюутнууд өөрсдийн сонгосон ямар ч $p$ ширхэг тушаалаа захирлуудын хурлаар батлуулж чадна. Мөн оюутнууд муухай ааштай захирал тэдгээр $p$ тушаалын яг $k$-г биелүүлнэ гэдгийг мэдэж байгаа юм. Тэрээр 1-т захирлуудын дургүйцэл, 2-т түүний бууралтах үсний тоо хамгийн бага байхаар тушаалуудыг сонгож биелүүлнэ.

Оюутнууд муухай аашт захирлын бууралтах үсний тоо нь хамгийн их байхаар $p$ ширхэг тушаал сонгох юм. Хэрэв ийм байхаар тушаалуудыг сонгох олон арга байвал оюутнууд нь муухай аашт захиралд уурлах захирлуудын дургүйцэл нь хамгийн их байхаар сонгох юм. Тэдэнд тусална уу.

Оролт

Эхний мөрөнд харгалзан захирлуудын хэлэлцэх тушаалын тоо, муухай аашт захирлын хүлээн авах тушаалын тоо болон биелүүлэх тушаалын тоог илэрхийлэх 3-н бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$), $p$ ($1 ≤ p ≤ n$), $k$ ($1 ≤ k ≤ p$) өгөгдөнө. Дараагийн $n$ мөрийн мөр болгонд 2 бүхэл тоо $a_{i}$ болон $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 10^{9}$) өгөгдөх ба эдгээр нь тушаалуудыг илэрхийлнэ.

Гаралт

Оюутнуудын өшөөгөө авч чадах тушаалуудын дугаар болох ялгаатай $p$ ширхэг бүхэл тоог дурын дарааллаар хэвлэнэ. Тушаалууд нь оролтод өгөгдсөн дарааллаараа 1-ээс $n$ хүртэл индекслэгдсэн байх юм. Хэрэв олон хариултууд байвал та тэдгээрийн алийг нь ч хэвлэсэн болно.

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

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

Оролт
5 3 2
5 6
5 8
1 3
4 3
4 11
Гаралт
3 1 2 
Оролт
5 3 3
10 18
18 17
10 20
20 18
20 18
Гаралт
2 4 5 

Тэмдэглэл

Эхний жишээний нэгэн оновчтой хариулт нь 1, 2, 3 гэсэн тушаалуудыг захиралд өгөх юм. Энэ тохиолдолд муухай аашт захирал 1 болон 2 дугаартай тушаалуудыг биелүүлэх ба тэрээр шинээр 10-н ширхэг шинэ буурал үстэй болох ба захирлуудын дургүйцэл нь 3-тай тэнцүү байх юм. 3 дугаартай тушаалын оронд 4 дугаартай тушаалыг сонгосноор ижил үр дүнд хүрч болохыг анхаарна уу.

2-дахь жишээнд, муухай аашт захирал нь бүх тушаалыг биелүүлэх ба иймд оюутнуудын хамгийн оновчтой сонголт нь хамгийн их $a_{i}$ утгуудын нийлбэртэй тушаалуудыг сонгох юм. Ингэснээр захирал 58-н ширхэг шинэ буурал үстэй болох ба захирлуудын дургүйцэл нь 0-тэй тэнцүү байна.

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