팀 워크

UCF 프로그래밍 팀은 40년이 넘는 기간 동안 좋은 성적을 거두었다. 재능 있고 헌신적인 학생들과 경험이 많고 뛰어난 코치들 덕분이다. 코치들은 여러 알고리즘과 팀 전략을 가르치고, 학생들은 다양한 대회에서 실력을 겨룬다.

International Collegiate Programming Contest에 나가는 팀은 학생 세 명으로 구성된다. 팀 전략 중 하나는 어떤 학생이 어떤 문제를 풀지 정하는 것이다. 코치들은 이 질문에 답해 주는 프로그램이 필요하다. 그 프로그램을 작성하라.

팀의 학생 수, 문제 수, 학생별로 각 문제를 푸는 데 걸리는 시간, 대회의 총 시간이 주어진다. 주어진 시간 안에 팀 전체가 풀 수 있는 문제 수의 최댓값을 구하라. 다음을 가정한다.

• 학생은 대회 전체에서 최대 한 문제만 풀 수 있다. 예를 들어 대회 시간이 5시간이고, 학생 1이 문제 7을 1시간, 문제 9를 2시간에 풀 수 있다고 하자. 두 문제를 합쳐 3시간이면 대회 시간 안에 끝나지만, 이 학생은 여전히 한 문제만 풀 수 있다.
• 팀에는 컴퓨터가 한 대뿐이다. 한 학생이 컴퓨터를 쓰는 동안 팀원은 컴퓨터를 쓸 수 없다. 따라서 문제는 한 번에 하나씩 풀린다. 예를 들어 대회 시간이 5시간이고, 학생 2가 문제 6을 2시간에, 학생 3이 문제 8을 4시간에 풀 수 있다고 하자. 두 문제는 합쳐 6시간이 필요하므로 5시간 대회에서는 둘 다 풀 수 없다. 학생이 여럿이어도 문제는 병렬로 풀지 않고 하나씩 푼다.

첫 줄에 세 정수 $n$, $p$, $t$가 주어진다.

• $n$ ($1 \le n \le 200$): 팀의 학생 수
• $p$ ($1 \le p \le 200$): 문제의 수
• $t$ ($1 \le t \le 10^5$): 사용할 수 있는 총 시간

다음 $n$개의 줄에는 각각 정수 $p$개가 주어진다. $i$번째 줄은 학생 $i$의 정보이며, 그 줄의 $j$번째 정수는 학생 $i$가 문제 $j$를 푸는 데 걸리는 시간이다. 각 값은 0 이상 $10^5$ 이하이다. 0은 그 학생이 그 문제를 풀지 못한다는 뜻이다.

주어진 시간 안에 팀 전체가 풀 수 있는 문제 수의 최댓값을 출력한다.