Một trò chơi truyền hình được ưa thích gần đây 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ố 𝑛, 𝑇;
- Dòng 2: gồm 𝑛 số nguyên, số thứ 𝑖 là 𝑎_𝑖 nghĩa là tại cửa thứ i người chơi sẽ nhận được 𝑎_𝑖 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.