DEI policies P96297

A distant math faculty is implementing new DEI (Diversity, Equity, and Inclusion) policies, to the joy of its members. Lots of math-unrelated posters are now decorating the walls, and the urinals have been covered in eco-friendly plastic bags to make bathrooms gender neutral. Everybody loves it!

Alas, some evil weirdo is not so thrilled, and he is planning to boycott all these absolutely fantastic positive amazing changes. His atrocious strategy is as follows: he will rip off one of the posters from the wall, and then run to one of the toilets, where he will use the poster to clog it. Then he will run to another poster, rip it off, run to another toilet, and so on. The vandal will never carry more than one poster, and he will never go twice to a poster position or to a toilet. He thinks that if he clogs k of the toilets, the queues to use the remaining ones will get so bad that the urinals will need to become available again. What a fool!

The twisted ruffian has calculated the time he would take to go between each of the n toilets and each of the m posters (the same in both directions), and asks you to plan his movements. Being on the side of good, progress and moral enlightenment, you will make sure to give him the worst possible time to complete his goal, with the hopes to maximize the chances he gets caught. Let’s make him wish he had stayed in his cave!

Input

Input consists of several cases, with the number of toilets n, the number of posters m, and ‍k. Follow n lines with m natural numbers each: the j-th number of the i-th line is the time that it takes to go between toilet i and poster j, in any direction. Assume that n and m are between 2 and 9, 1 ≤ k ≤ min(n, m), and that the times are between 1 and 10⁷.

Output

For every case, print the maximum time for the vandal to clog k toilets.