Một trò chơi 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 số tiền ở cửa đó. Tuy nhiên người chơi có thể trả \(k \cdot 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à luôn 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 tiền).

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ể thì phải mất ít nhất bao nhiêu bước.

Input

• Dòng 1: chứa hai số nguyên \(n, T\).
• Dòng 2: 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.

Output

• Số bước nhỏ nhất nếu có thể qua được và \(-1\) nếu không có cách qua.

Example

1 100
100

1

1 100
-20

-1

4 100
120 20 20 20

3

6 100
30 30 30 30 30 30

5

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 20; |a_i| \le 100\).
• Subtask \(2\) (\(25\%\) số điểm): \(n \le 100; |a_i| \le 100\).
• Subtask \(3\) (\(25\%\) số điểm): \(n \le 100; |a_i| \le 10^9\).
• Subtask \(4\) (\(25\%\) số điểm): \(n \le 2000; |a_i| \le 10^9\).