THỰC HÀNH

Một gameshow truyền hình được ưa thích gần đây như sau: Có n cửa cần vượt qua, tại mỗi cửa người chơi sẽ nhận được (hoặc mất) một số tiền tương ứng với cửa đó. Tuy nhiên người chơi có thể trả k × T đồng để bỏ qua k cửa. Để vượt qua n cửa này, người chơi phải bắt đầu từ cửa thứ nhất và kết thúc tại cửa thứ n mà trên đường đi của mình không khi nào bị “âm” tiền. Ban đầu người chơi “rỗng túi” (có 0 đồng).

Yêu cầu: Bạn hãy kiểm tra xem, với một hệ thống các cửa cho trước thì người chơi có thể vượt qua n cửa hay không và nếu có thì phải mất ít nhất bao nhiêu bước.

Input:

• Dòng một ghi hai số nguyên n và T
• Dòng hai gồm n số nguyên, số thứ i là a_i nghĩa là tại của thứ i người chơi sẽ nhận được a_i tiền (nếu a_i > 0, sẽ mất a_i tiền nếu a_i < 0)

Output:

• Nếu có thể qua được thì ghi số bước nhỏ nhất, nếu không qua được thì ghi -1

Ví dụ:

Input:
1 100
100
Output:
1

Input:
1 100
-20
Output:
-1

Input:
4 100
120 20 20 20
Output:
3

Input:
6 100
30 30 30 30 30 30
Output:
5

Giới hạn:

• Subtask 1: n ≤ 20, |a_i| ≤ 100
• Subtask 2: n ≤ 100, |a_i| ≤ 100
• Subtask 3: n ≤ 100, |a_i| ≤ 10⁹
• Subtask 4: n ≤ 5000, |a_i| ≤ 10⁹