Mosaic Mansion

Time limit12sMemory limit512 MB

Summary
Given n rows of m colored tiles, remove rows so that the kept rows contain the same number of tiles of each color; maximize the number of kept rows.
Level

Hard8 of 10

Topics
Dynamic programming, Hash map, Combinatorics, Math
Solved
No attempts yet

Problem

A mosaic is a picture made from square tiles arranged in a grid, at least for today’s purposes.

We would like to make a mosaic with exactly the same number of tiles of each colour. We will do this by taking an existing design and removing some of the rows from it.

Figure M.1: Illustration of a solution to Sample Input 1. The three rows annotated with white can be kept, giving 6 of each colour of tile.

What is the greatest number of rows we can keep?

Input

  • The first line of input contains the number of rows, n (1 ≤ n ≤ 40), the number of columns, m (1 ≤ m ≤ 105), and the number of colours, c (1 ≤ c ≤ 105) in the mosaic respectively.
  • Each of the next n lines contains m colours of cells p1 . . . pm (1 ≤ p ≤ c).

Output

Output the greatest number of rows that can be kept while keeping equal representation for each colour in the input, or 0 if no rows can be kept.

Examples1

  1. Example 1

    Input
    4 10 5
1 2 1 2 3 1 2 3 4 3
5 2 5 3 5 5 5 5 1 4
2 3 2 1 4 3 3 2 1 4
1 2 3 4 4 4 4 1 2 3
    Expected output
    3