Cắt dãy

View as PDF
Submit solution
Points: 0.79 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho số nguyên ~N~ và một dãy số nguyên ~a_{1}, a_{2}, ..., a_{N}~. Nhiệm vụ của bạn là phải cắt dãy số trên thành một số dãy số (giữ nguyên thứ tự) thỏa mãn:

  • Tổng của mỗi dãy số không lớn hơn số nguyên ~M~.
  • Tổng của các số lớn nhất trong các dãy trên là nhỏ nhất.

Input

  • Dòng đầu gồm ~2~ số nguyên ~N~ và ~M~.
  • Dòng thứ hai gồm ~N~ số nguyên của dãy ~a_{1},a_{2}, ..., a_{N}~.

Output

Gồm một số duy nhất là tổng của các số lớn nhất trong các dãy số trên. Nếu không có cách cắt nào thỏa mãn hai điều kiện trên, in ra ~-1~.

Giới hạn

Giới hạn:

  • ~1 \le N \le 100000~.
  • ~0 \le a_{i} \le 10^{6}~.
  • ~M < 2^{63}~.

Sample Input

8 17
2 2 2 8 1 8 2 1

Sample Output

12

Note

Giải thích: Cắt thành ~3~ dãy ~2 2 2, 8 1 8, 2 1~

Comments

Please read the guidelines before commenting.


  • -1
    hieuhfgr  commented on May 21, 2024, 8:07 a.m.

    tét ye'u qua' 2 for ac ma ru`i :<>


    • -3
      khanhlani  commented on May 23, 2024, 7:14 a.m.

      Xam


  • 2
    PM  commented on Jan. 21, 2024, 2:59 a.m.

    test yếu quá mình làm 2 for cũng AC


  • 4
    1729  commented on Sept. 18, 2023, 2:59 a.m.

    admin có thể add thêm 1 test dãy giảm dần 1e5 phần tử và m=s^63 -1 được ko


    • -1
      1502dth  commented on Sept. 18, 2023, 3:00 a.m.

      nờ ô nô


  • 0
    hodinhhoang312  commented on April 28, 2021, 2:36 p.m.

    test yếu quá :<


    • -7
      leduykhongngu  commented on April 29, 2021, 2:57 a.m. ← edited

      This comment is hidden due to too much negative feedback. Show it anyway.