Buôn dưa lê

Submit solution
Points: 3
Time limit: 1.0s
Python 3 2.0s
Memory limit: 98M
Author:
TICHPX
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Đại dịch covid-19 ùa đến quá nhanh, làng Quẹo trồng rất nhiều dưa lê nhưng mọi người phải đi cách ly nên không có ai thu hoạch. Tito quyết định dồn tiền mua hết dưa lê của cả cánh đồng Quẹo. Cách đồng Quẹo có \(n\) thửa ruộng được đánh số từ \(1\) đến \(n\), mỗi thửa ruộng thứ \(i\) thì bắt đầu được thu hoạch từ ngày thứ thứ \(i\) nếu thu hoạch đúng trong vòng \(k\) ngày sẽ thu được sản lượng là \(a_i\) nếu quá k ngày thì dưa lê sẽ bị hỏng. Mà năng lực có hạn nên mỗi ngày Tito chỉ thu hoạch được tối đa \(m\) sản lượng. Bạn hãy tính tổng sản lượng có thể lớn nhất mà TiTo thu hoạch trên cánh đồng này.

Input

Dòng đầu chứa \(n,k,m\) tương ứng là số thửa ruộng, số ngày tối đa mà dưa phải thu hoạch cho mỗi thửa và năng lực của Tito \((1 \le n,m,k \le 10^5)\)

Dòng thứ 2 chứa \(n\) giá trị là sản lượng lần lượt dưa lê chín trong từng ngày từ \(1\) đến \(n\) các giá trị \(a_i\) với \((1 \le a_i \le 10^9)\)

Output

Một số nguyên duy nhất là tổng tối đa sản lượng mà Tito có thể thu hoạch được

Ví dụ

Input

6 2 5
4 7 2 18 1 10

Output

33

Giải thích :

Có 6 thửa ruộng, từ khi dưa lê bắt đầu chín thì chỉ được thu hoạch trong vòng 2 ngày và năng lực thu hoạch mỗi ngày chỉ là 5 đơn vị sản lượng

  • Ngày 1 dưa lê chín 4 mà năng lực 5 nên Tito sẽ thu được 4

  • Ngày 2 dưa lê chín 7 mà năng lực 5 nên Tito sẽ thu được 5 còn lại 2 để sang ngày 3

  • Ngày 3 dưa lê chín 2 cộng thêm 2 của ngày trước (chưa hỏng) mà năng lực 5 nên Tito sẽ thu được 4

  • Ngày 4 dưa lê chín 18 mà năng lực 5 nên chỉ thu được 5 còn thừa 13 để sang ngày 5

  • Ngày 5 Tito tập trung thu hoạch 5 của ngày 4 vì để quá 2 ngày sẽ hỏng nên 13 này chỉ thu được 5 còn lại phải bỏ đi, như vậy chỉ có 1 sản lượng chín vào ngày này đành để lại sang ngày 6 thu hoạch

  • Ngày 6 Tito thu hoạch 1 sản lượng chín từ ngày 5 và 4 sản lượng chín từ ngày 6 nên sẽ được 5 sản lượng do đó còn 6 sản lượng để sang ngày 7

  • Ngày 7 Tito sẽ thu hoạch 5 sản lượng chín từ ngày 6 tất nhiên 1 sản lượng còn lại sẽ bị hỏng

Như vậy tổng số sản lượng Tito thu được là 4+5+4+5+5+5+5 = 33

tichpx

Comments


  • 1
    NguyenDongThinh_CNTT4_K61  commented on Nov. 13, 2021, 5:03 p.m.

    ai làm đc rồi cho mình xin gợi ý đc khum ạ :<


    • 4
      TICHPX  commented on Nov. 14, 2021, 6:12 a.m.

      Ý tưởng tham lam em ạ, cái nào chín trước thu trước nhưng thu không hết thì xếp vào queue hoặc list để hôm sau thu tiếp


    • 0
      sguenm  commented on Nov. 14, 2021, 5:57 a.m.

      ý tưởng ban đầu của t là tạo 1 biến lưu tổng dưa có thể thu hoạch, 1 biến lưu tổng dưa đã thu hoạch. xét n+k-1 ngày, ngày nào dư ra thì sẽ cộng vào chỗ có thể thu hoạch. chỗ dưa hỏng sẽ bị trừ vào biến đã thu hoạch rồi, trừ hết thì trừ sang biến có thể thu hoạch