30205번 - 전역 임무

김 병장이 소속된 특수부대는 전역을 하려면 특이하게 대대장으로부터 주어진 임무를 달성해야 한다. 김 병장이 받은 임무는 적군의 $1$번 기지부터 $N$번 기지까지 모두 순서대로 격파하는 것이다. 각 기지는 $M$층으로 이루어져 있고, 기지에 입장하면 $1$층부터 $M$층까지 순서대로 한 층씩 올라가야 하며, 중간에 아래층으로 내려가거나 나갈 수 없다. 만약에 무사히 $M$층까지 도달하여 기지 내의 적군들을 모두 쓰러트렸다면, 해당 기지는 격파되었다고 한다.

적군 기지의 각 층에는 아이템과 적군 중 하나가 배치되어 있다. 김 병장이 아이템이 배치된 층에 진입하면, 즉시 김 병장의 전투력이 두 배로 늘어난다. 김 병장이 적군이 배치된 층에 진입하면, 해당 적군과 전투한다. 만약 적군의 전투력이 김 병장의 전투력 이하라면, 김 병장이 전투에서 승리하고 적군의 전투력만큼 김 병장의 전투력이 증가한다. 그렇지 않으면, 김 병장은 임무에 실패한다.

임무를 수월하게 달성하기 위해서 김 병장은 같은 기지 안에 있는 층들의 순서를 마음대로 바꿀 수 있는 마법을 배워왔다. 김 병장의 현재 전투력이 주어졌을 때, 마법을 사용해 임무를 달성할 수 있는지 알아보자.

첫 번째 줄에는 격파해야 할 적군 기지의 수 $N$, 각 기지의 층수 $M$, 현재 김 병장의 전투력 $P$가 공백으로 구분되어 정수로 주어진다. $(1 \le N \le 500;$ $1 \le M \le 500;$ $1 \le P \le 10^{9})$

이후 $N$개의 줄에 걸쳐, 순서대로 격파해야 하는 기지의 정보 $s_{ij}$가 각 줄마다 $M$개씩 공백으로 구분되어 정수로 주어진다. $(-1 \le s_{ij} \le 10^{9})$

그중 $i$번째 줄은 $i$번째로 격파해야 하는 기지의 정보이며, $i$번째 줄의 $j$번째 값 $s_{ij}$는 $i$번째로 격파하는 기지의 $j$번째 층에 대한 정보를 나타내는 정수이다. 만약에 $s_{ij} = -1$이라면 해당 층에 아이템이 있는 것이며, $s_{ij} \ge 0$이라면 $s_{ij}$만큼의 전투력을 가진 적군이 해당 층에 있다는 것이다.

임무 종료 이후의 김 병장의 전투력이 $10^{18}$을 초과하면서 모든 기지를 격파할 수 있는 입력은 주어지지 않는다.

김 병장이 임무를 달성할 수 있다면 1, 아니면 0을 출력한다.