Facility Locations

Time limit1sMemory limit256 MB

Summary

Decide whether k candidate locations can be chosen so every client is served at zero cost.

Level: Medium6 of 10
Topics: Union-find, Math
Solved: No attempts yet

Problem

A company has $n$ clients and must serve all of them by opening $k$ facilities. An open facility serves any number of clients, and every client is assigned to one open facility. There are $m$ candidate locations for the facilities. Serving client $j$ from candidate location $i$ costs a non-negative integer $c_{ij}$ , and the costs satisfy a locality condition: for any clients $j$ and $j'$ and any candidate locations $i$ and $i'$ , $c_{ij} \le c_{i'j} + c_{i'j'} + c_{ij'}$ holds.

The company eventually wants the cheapest way to open $k$ facilities. Right now it needs the answer to an earlier question. Decide whether it can open $k$ facilities and assign every client at a total cost of zero.

Input

The first line contains the integers $m$ , $n$ , $k$ , separated by spaces. ( $1 \le m \le 100$ , $1 \le n \le 100$ , $1 \le k \le m$ )

Line $i$ of the next $m$ lines contains $n$ non-negative integers, the $j$ -th of which is $c_{ij}$ . ( $0 \le c_{ij} \le 10000$ )

Output

Print yes if the company can open $k$ facilities and assign every client at a total cost of zero. Otherwise print no.

Examples2

Example 1
Input
```
3 2 2
0 2
1 1
2 0
```
Expected output
```
yes
```
Example 2
Input
```
3 3 2
0 2 2
1 1 1
2 2 0
```
Expected output
```
no
```