Tiểu C đang chơi một trò chơi dàn trận. Trong trò chơi có $n$ tòa thành, mỗi ván đấu sẽ có hai người chơi tranh giành các tòa thành này. Mỗi người chơi có $m$ binh lính, có thể cử $a_i$ binh lính đến tòa thành thứ $i$ để tranh giành tòa thành đó, sao cho tổng số binh lính không vượt quá $m$.

Nếu một người chơi cử số binh lính đến tòa thành thứ $i$ nhiều hơn gấp đôi số binh lính mà đối thủ cử đến, thì người chơi đó sẽ chiếm được tòa thành này và nhận được $i$ điểm.

Hiện tại, Tiểu C sắp đối đầu với $s$ người chơi khác theo thể thức đấu cặp, và phương án cử binh lính cho $s$ ván đấu này phải giống hệt nhau. Tiểu C đã biết trước chiến thuật mà $s$ người chơi kia sẽ sử dụng, cậu ấy muốn biết mình nên sử dụng chiến thuật nào để tối đa hóa tổng số điểm của bản thân.

Vì đáp án có thể không duy nhất, bạn chỉ cần xuất ra giá trị lớn nhất của tổng số điểm mà Tiểu C có thể đạt được.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên dương $s, n, m$, lần lượt là số lượng người chơi khác, số lượng tòa thành và số lượng binh lính mỗi người chơi sở hữu.

$s$ dòng tiếp theo, mỗi dòng chứa $n$ số nguyên không âm, biểu thị chiến thuật của một người chơi, trong đó số thứ $i$ là $a_i$ biểu thị số binh lính người chơi đó cử đến tòa thành thứ $i$.

Dữ liệu ra

Xuất ra một dòng chứa một số nguyên không âm, là tổng số điểm tối đa mà Tiểu C có thể đạt được.

Ví dụ

Dữ liệu vào 1

1 3 10
2 2 6

Dữ liệu ra 1

3

Ghi chú

Chiến thuật tối ưu của Tiểu C là cử $5$ binh lính đến tòa thành thứ $1$ và $5$ binh lính đến tòa thành thứ $2$.

Dữ liệu vào 2

2 3 10
2 2 6
0 0 0

Dữ liệu ra 2

8

Ghi chú

Một trong những chiến thuật tối ưu của Tiểu C là cử $2$ binh lính đến tòa thành thứ $1$, $5$ binh lính đến tòa thành thứ $2$ và $1$ binh lính đến tòa thành thứ $3$.

Nhiệm vụ con

Với $10\%$ dữ liệu, đảm bảo $s=1, n \le 3, m \le 10$.

Với $20\%$ dữ liệu, đảm bảo $s=1, n \le 10, m \le 100$.

Với $40\%$ dữ liệu, đảm bảo $n \le 10, m \le 100$.

Với $20\%$ dữ liệu khác, đảm bảo $s=1$.

Với $100\%$ dữ liệu, đảm bảo:

• $1 \le s \le 100$
• $1 \le n \le 100$
• $1 \le m \le 2 \times 10^4$
• Với mỗi người chơi, $a_i \ge 0, \sum\limits_{i=1}^n a_i \le m$.