ARTFLOWER - Cắm hoa nghệ thuật
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: a516 Thánh Ngốc

Cho N lọ hoa và K bông hoa (N<=K).

Hãy chọn ra N bông hoa từ K bông hoa đã cho theo thứ tự tăng dần rồi cắm vào các lọ hoa từ 1 đến N. Biết khi cắm bông hoa j vào lọ thứ i thì sẽ có điểm nghệ thuật là A[i][j]. Hãy tìm điểm nghệ thuật tối đa có thể đạt được. 

Dữ liệu:

Input:

    Dòng đầu tiên chứa 2 số N,K (N<=K<=5000)

    N dòng tiếp theo, mỗi dòng chứa K số, số thứ j trong dòng thứ iA[i][j].

Output:

    Điểm nghệ thuật tối đa.

 

Ví dụ

  • input
    2 4
    10 1 9 2
    6 7 7 10
    output
    20

Chọn bông hoa 1,4
Cắm bông hoa thứ 1 vào lọ 1 được điểm nghệ thuật: A[1][1] = 10
Cắm bông hoa thứ 4 vào lọ 2 được điểm nghệ thuật: A[2][4] = 10

Tổng điểm nghệ thuật là 10+10=20

Back to Top