전역 임무

김 병장이 소속된 특수부대는 전역하려면 대대장이 준 임무를 달성해야 한다. 김 병장이 받은 임무는 적군의 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$개의 줄에 걸쳐 순서대로 격파해야 할 기지의 정보가 주어진다. $i$번째 줄은 $i$번째로 격파할 기지의 정보이며, 그 줄의 $j$번째 값 $s_{ij}$는 그 기지의 $j$층에 대한 정보이다. 각 줄에는 $M$개의 값이 공백으로 구분되어 있다. $s_{ij} = -1$이면 해당 층에 아이템이 있다는 뜻이고, $s_{ij} \ge 0$이면 전투력이 $s_{ij}$인 적군이 해당 층에 있다는 뜻이다. $(-1 \le s_{ij} \le 10^{9})$

임무를 마친 뒤 김 병장의 전투력이 $10^{18}$을 넘으면서 모든 기지를 격파할 수 있는 입력은 주어지지 않는다.

김 병장이 임무를 달성할 수 있으면 1을, 그렇지 않으면 0을 출력한다.