SJSU Weekly Practice Problems 1/2

#### Start

2022-01-02 20:00 AKST

## SJSU Weekly Practice Problems 1/2

#### End

2022-01-09 20:00 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -139 days 22:00:37

168:00:00

0:00:00

# Problem IFacility Locations

Picture from Wikimedia Commons

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 $j’$ and two facilities $i$ and $i’$, we have $c_{ij} \le c_{i'j} + c_{i'j'} + c_{ij'}$. 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

The input consists of a single test case. The first line contains three integers $m$, $n$, $k$ where $1 \le m \le 100$, $1 \le n \le 100$ and $1 \le k \le m$. Each of the next $m$ lines contains $n$ non-negative integers where the $j$th integer in the $i$th line is $c_{ij} \le 10\, 000$.

## Output

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

Sample Input 1 Sample Output 1
3 2 2
0 2
1 1
2 0

yes

Sample Input 2 Sample Output 2
3 3 2
0 2 2
1 1 1
2 2 0

no