Giải bài trực tuyến

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

Cho ma trận giá cổ phiệu hiện tại và tương lai trong những ngày khác nhau (1 <= PR_sd <= 1,000) vag một lượng M (1 <= M <= 200,000) đơn vị tiền , hãy xác định chiến thuật mua và bán để có tối đa lợi nhuận nhận được trong ngày cuối cùng. Những cổ phiếu cần được mua trong một lượng nguyên, và bạn không cần sử dụng tất cả số tiền hoặc có thể bạn không cần mua. Người ta đảm bảo đảm rằng lời nhuận kiếm được không vượt quá 500,000 đơn vị tiền.

Nếu tiền được đầu tư: các chú bò mua cổ phiếu 1 vào ngày 1. Bán cổ phiếu 1 vào ngày 2 và nhanh chón mua cổ phiếu 2 như vậy có 4 đơn vị tiền trong nhà băng và một cổ phiếu loại 2. Cuối cùng, bán cổ phiếu 2 vào ngay cuối cùng th được 20 đơn vị tiền và sẽ có 24 đơn vị tiền trong nhà băng.

Dữ liệu

* Dòng 1: Ba số nguyên được các nhau: S, D, and M (S < 51, D < 11)

* Dòng 2..S+1: dòng s+1 gồm D giá cho cổ phiếu s trong ngày 1..D: PR_sd

Kết quả

* Dòng 1: Số lượng tiên lớn nhất có thể có sau D sau khi bán trong ngày D.

Ví dụ

Dữ liệu:

2 3 10
10 15 15
13 11 20

Kết quả

24