D. R2D2 ба робот арми

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

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

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

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

Нэг эгнээ жагссан $n$ тооны робот байв. Робот бүр $m$ ширхэг $a_{1}, a_{2}, ..., a_{m}$ бүхэл тоонуудаар тодорхойлогддог ба $a_{i}$ бол энэ роботын механизмд байгаа $i$-р төрлийн эд ангийн тоо юм. R2-D2 (Artoo-Detoo буюу Starwars киноны дүр) хамгийн урт дараалсан роботуудын дарааллыг устгахыг хүссэн. Түүнд $m$ ширхэг зэвсэг байгаа бөгөөд $i$-р зэвсгээр бүх роботоос нэгэн зэрэг $i$-р төрлийн (хэрвээ роботод энэ төрлийн эд анги байхгүй бол ямар ч нөлөө байхгүй) нэг эд ангийг устгах боломжтой.

Роботын бүх эд ангиуд устгагдсан тохиолдолд түүнийг устсан гэж үзнэ. R2-D2 хамгийн ихдээ $k$ буудалт хийж болно. R2-D2 хамгийн урт дараалсан роботуудын дарааллыг устгахын тулд ямар ямар төрлийн зэвсгээр тус бүр хэдэн удаа буудах вэ?

Оролт

Эхний мөрөнд $n, m, k$ ($1 ≤ n ≤ 10^{5}$, $1 ≤ m ≤ 5$, $0 ≤ k ≤ 10^{9}$) гурван бүхэл тоо байна. Эдгээр нь харгалзан роботуудын тоо, эд ангиудын төрлийн тоо болон боломжтой буудалтын тоо юм.

Дараагийн $n$ мөрүүдэд роботуудыг тодорхойлно. Мөр бүр $m$ ширхэг $a_{1}, a_{2}, ..., a_{m}$ ($0 ≤ a_{i} ≤ 10^{8}$) бүхэл тоонуудыг агуулах ба $a_{i}$ нь харгалзах роботын $i$-р төрлийн эд ангийн тоог илэрхийлнэ.

Гаралт

Зайгаар тусгаарлагдсан $m$ ширхэг бүхэл тоонууд хэвлэх ба $i$-р тоо нь хамгийн урт дараалсан роботуудын дэд дарааллыг устгахын тулд роботыг $i$-р төрлийн зэвсгээр буудах тоо юм.

Хэрвээ хэд хэдэн шийд байгаа бол тэдгээрийн аль нэгийг хэвлэнэ.

Заавал $k$ удаа буудах шаардлагагүй, түүнээс бага буудаж болно.

Орчуулсан: Даариймаа

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

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

Тэмдэглэл

Эхний жишээнд хоёр, гурав, дөрөвдүгээр роботууд устгагдсан.

Хоёрдахь жишээнд нэг, хоёрдугаар роботууд устгагдсан.

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