Under construction

Still being built. Things may change

Reapportionment

Time limit7sMemory limit1024 MB

Summary
Given block populations in a rectangular town, decide whether the blocks can be split into W contiguous wards with equal total population.
Level

Medium6 of 10

Topics
Backtracking, Brute force, Graph
Solved
No attempts yet

Problem

Here is an example of a small town made of 5×5=255 \times 5 = 25 blocks with a population of 99. The colors highlight one way to divide the town into 3 contiguous wards of 33 citizens each. Your task is to consider towns of various sizes and determine whether the blocks can be divided into contiguous wards of equal population. All towns are rectangular and have no more than 25 blocks. The number of desired wards may vary. Two blocks are adjacent if they share an edge. A contiguous ward is a set of blocks such that, starting from any one block and moving only to adjacent blocks in the ward, you can reach every block in the ward.

Input

The first line contains two integers RR and CC (1≤R×C≤251 \leq R \times C \leq 25), the number of rows and columns of the rectangular town. The next line contains an integer WW (1≤W≤R×C1 \leq W \leq R \times C), the number of wards desired. The next RR lines each contain CC non-negative integers, the populations of the blocks in each row, starting from the top row. Blocks in each row are listed from left to right. The total population of the town is no more than 1,000,0001{,}000{,}000.

Output

If the reapportionment is possible with the given input, print "Yes". Otherwise, print "No".

Examples1

  1. Example 1

    Input
    5 5
3
1 4 12 7 5
8 10 9 1 2
2 4 1 2 3
3 3 5 4 3
1 2 4 2 1
    Expected output
    Yes