E. Кубүүд

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

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

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

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

Та доорх энгийн компьютер тоглоомыг тоглож байгаа гэж саная. Дэлгэц дараалсан $n$ кубээс тогтоно. Куб бүр $m$ өнгүүдийн аль нэгээр будагдсан. Та $k$ кубээс олныг устгаж болохгүй (дарааллан устгах албагүй). Дараагаар нь үлсдэн кубүүд холбож (хоосон зайг битүүлнэ), систем оноог тооцдог. Таны авах оноо дааралан байрлах ижил өнгөтэй кубуудын хамгийн их дарааллын урттай тэнцэнэ. Авч болох хамгийн өндөр оноог тооцоолох програм бич.

$k$ кубээс илүүг устгаж болохгүй гэдгийг санах хэрэгтэй. Ямар кубыг устгахгүй байсан ч болно.

Оролт

Эхний мөр $n, m, k (1 <= n <= 2 * 10^5, 1 <= m <= 10^5, 0 <= k < n)$ гурван бүхэл тоог агуулна. Хоёр дугаар мөрөнд кубүүдийн өнгөний тоо 1-ээс $m$ хүртэлх $n$ бүхэл тоо байна. Өнөгний тоонууд нь ганц хоосон зайгаар тусгаарлагдана.

Гаралт

Авч чадах хамгийн их оноог хэвлэнэ.

Орчуулсан: devman

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

Оролт
10 3 2
1 2 1 1 3 2 1 1 2 2
Гаралт
4
Оролт
10 2 2
1 2 1 2 1 1 2 1 1 2
Гаралт
5
Оролт
3 1 2
1 1 1
Гаралт
3

Тэмдэглэл

Эхний жишээнд та 5, 6-р кубүүдийг устгах хэрэгтэй.

Хоёр дугаар жишээнд 4, 7-р кубүүдийг устгах хэрэгтэй.

Гурав дугаар жишээнд ямар куб устгах шаардлагагүй.

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