|
В поисках родной планеты Фурия неутомимого Риддика занесло на странную планету, кишащую монстрами различных мастей. Как оказалось, видов монстров на планете целых N. Чтобы выжить, нужно было предпринимать какие-то действия.
Риддику пришла в голову идея тайком украсть по одному детенышу от монстра каждого вида и вырастить из них собственную армию - тогда на этой планете ему будет гораздо спокойнее и безопаснее. Единственная проблема в том, что Риддик может позволить себе заниматься воспитанием не более чем K монстров - на большее просто не хватит никакого времени!
Вместе с тем, Риддик заинтересован в максимальной мощи своей армии. К счастью, про каждого монстра Риддик знает список присущих ему навыков, а всего навыков может быть не более T. Мощь армии определяется количеством различных навыков монстров, представленных в армии.
Вашей задачей будет сообщить, на какую максимальную мощь армии может рассчитывать Риддик. С математическими расчетами у Риддика не очень, зато есть умение убеждать и отличный удар с правой. К счастью, у Вас есть несколько часов, чтобы подумать и помочь Риддику. Время пошло!
Input
В первой строке содержатся три числа - N (1 <= N <= 1000), K (1 <= K <= N), T (1 <= T <= 12).
В следующих N строках содержится по T чисел в каждой. j-е число в i-й строке может быть равно 0 или 1. Значение 0 соответствует отсутствию у монстра под номером i навыка с номером j, значение 1 - наличию.
Output
Одно целое число - максимально возможная мощь войска Риддика.
Sample
| Input | Output |
|---|
3 2 3
0 1 0
0 1 0
0 0 1
|
2
|
6 2 8
0 0 0 1 1 0 0 0
0 0 1 0 0 1 0 0
0 1 0 0 0 0 1 0
1 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
|
4
|
| 