Một trò chơi truyền hình được Đức Tuấn rất ưa thích như sau: Có 𝑛 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ả 𝑘 × 𝑇 đồng để bỏ qua 𝑘 cửa. Để vượt qua 𝑛 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ứ 𝑛 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 𝑛 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: là số 𝑛, 𝑇 ( n <= 5000 );

Dòng 2: gồm 𝑛 số nguyên, số thứ 𝑖 là a[i] nghĩa là tại cửa thứ i người chơi sẽ nhận được 𝑎[i] tiền( |a[i|] <= 10^9) .

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