eolymp
bolt
Try our new interface for solving problems
Problems

Facility Locations

Facility Locations

Time limit 1 second
Memory limit 122 MiB

The HDWBP Inc. has n clients and needs to service these clients by opening k facilities. Each opened facility can serve any number of clients and each client must be served by an open facility. There are m potential locations for these k facilities. The cost of serving client j at potential location i is a non-negative integer c[ij]. These costs satisfy a locality property: for two clients j and j0 and two facilities i and i0, we have c[ij]c[i0j] + c[i0j0] + c[ij0]. Given the costs, the CEO of HDWBP Inc. ultimately wants to know the cheapest way to open k facilities and assign clients to these open facilities. For now, he needs your help to determine if it is possible to do this task without any cost (i.e. with cost zero).

Input data

The first line contains three integers m, n, k where 1m100, 1n100 and 1km. Each of the next m lines contains n non-negative integers where the j-th integer in the i-th line is c[ij]10 000.

Output data

Display yes if it is possible to do the task with cost zero; otherwise, display no.

Examples

Input example #1
3 2 2
0 2
1 1
2 0
Output example #1
yes
Input example #2
3 3 2
0 2 2
1 1 1
2 2 0
Output example #2
no
Source 2014 ACM North America - Rocky Mountain, Problem D