Cho dù thông minh bẩm sinh nhưng những chú bò vẫn thất bại tại thị trường nhà trả góp, bây giờ chúng đang cố thử vận may ở cổ phiếu. Thật may mắn, Bessie là một nhà tiên tri và cô không chỉ biết giá của ~S~ ~(2 \le S \le 50)~ cổ phiếu trong hôm nay mà còn biết trước giá của chúng trong ~D~ ~(2 \le D \le 10)~ ngày tiếp theo.

Cho ma trận giá cổ phiếu trong nhiều ngày khác nhau ~(1 \le PR_{sd} \le 1000)~ và ~M~ ~(1 \le M \le 200\,000)~ đơn vị tiền. Hãy xác định một chiến thuật mua bán tối ưu để tối đa hoá lợi nhuận nhận được trong ngày cuối cùng. Những cố phiếu phải được mua theo lượng nguyên. Bạn không cần phải dùng hết toàn bộ số tiền (thậm chí bạn có thể không mua cổ phiếu nào). Dữ liệu đảm bảo lợi nhuận tối đa không vượt quá ~500\,000~ đơn vị tiền.

Input

• Dòng ~1~: Ba số nguyên cách nhau bởi dấu cách ~S~, ~D~ và ~M~.
• Dòng ~2~...~S + 1~: Dòng ~s + 1~ gồm ~D~ số nguyên ~PR_{sd}~ cho biết giá của cổ phiếu ~s~ trong ngày ~1~...~D~.

Output

In ra một dòng duy nhất chứa số tiền lớn nhất có thể đạt được sau khi bán tất cả cổ phiếu vào ngày ~D~.

Sample Input

2 3 10
10 15 15
13 11 20

Sample Output

24

Giải thích

Trong ví dụ, có ~S=2~ cổ phiếu và ~D=3~ ngày. Ban đầu đàn bò có ~10~ đơn vị tiền.

         Ngày 1
         |  Ngày 2
         |  |  Ngày 3
Cổ phiểu |  |  | 
  1      10 15 15
  2      13 11 20

Để tối đa hoá lợi nhuận, đàn bò phải mua cổ phiếu ~1~ vào ngày ~1~, sau đó bán cổ phiếu ~1~ và mua cổ phiếu ~2~ vào ngày ~2~, cuối cùng bán cổ phiếu ~2~ vào ngày ~3~.

Tổng số tiền đạt được là: ~10 - 10 + 15 - 11 + 20 = 24~.