소 C는 병력 배치 게임을 하고 있습니다. 게임에는 $n$개의 성이 있으며, 각 대국은 두 명의 플레이어가 이 성들을 차지하기 위해 경쟁합니다. 각 플레이어는 $m$명의 병사를 가지고 있으며, 제 $i$번 성에 $a_i$명의 병사를 파견하여 총 병사 수가 $m$을 넘지 않도록 할 수 있습니다.

한 플레이어가 제 $i$번 성에 파견한 병사 수가 상대방이 파견한 병사 수의 두 배를 엄격하게 초과하면, 해당 플레이어는 그 성을 점령하고 $i$점을 획득합니다.

이제 소 C는 다른 $s$명의 플레이어와 각각 일대일 대결을 펼칠 예정이며, 이 $s$번의 대결에서 사용할 병력 배치 전략은 모두 동일해야 합니다. 소 C는 다른 $s$명 플레이어의 전략을 미리 알고 있으며, 자신의 총점을 최대화하기 위해 어떤 전략을 사용해야 하는지 알고 싶어 합니다.

답이 유일하지 않을 수 있으므로, 소 C가 얻을 수 있는 총점의 최댓값만 출력하면 됩니다.

입력

입력의 첫 번째 줄에는 세 개의 양의 정수 $s, n, m$이 주어지며, 각각 소 C를 제외한 플레이어의 수, 성의 수, 각 플레이어가 보유한 병사 수를 나타냅니다.

이어지는 $s$개의 줄에는 각 줄마다 $n$개의 음이 아닌 정수가 주어지며, 이는 한 플레이어의 전략을 나타냅니다. 여기서 $i$번째 수는 해당 플레이어가 제 $i$번 성에 파견한 병사 수를 의미합니다.

출력

소 C가 얻을 수 있는 최대 점수를 나타내는 음이 아닌 정수 하나를 출력합니다.

예제

예제 입력 1

1 3 10
2 2 6

예제 출력 1

3

참고 1

소 C의 최적 전략은 제 $1$번 성과 제 $2$번 성에 각각 $5$명의 병사를 파견하는 것입니다.

예제 입력 2

2 3 10
2 2 6
0 0 0

예제 출력 2

8

참고 2

소 C의 최적 전략 중 하나는 제 $1$번 성에 $2$명, 제 $2$번 성에 $5$명, 제 $3$번 성에 $1$명의 병사를 파견하는 것입니다.

서브태스크

데이터의 $10\%$에 대해 $s=1, n \le 3, m \le 10$을 보장합니다.

데이터의 $20\%$에 대해 $s=1, n \le 10, m \le 100$을 보장합니다.

데이터의 $40\%$에 대해 $n \le 10, m \le 100$을 보장합니다.

데이터의 추가 $20\%$에 대해 $s=1$을 보장합니다.

데이터의 $100\%$에 대해 다음을 보장합니다.

• $1 \le s \le 100$
• $1 \le n \le 100$
• $1 \le m \le 2 \times 10^4$
• 각 플레이어에 대해 $a_i \ge 0, \sum\limits_{i=1}^n a_i \le m$입니다.