Sau khi hoàn thành việc xây dựng một dãy cầu tuyết đối xứng tuyệt đẹp, ABNL quyết định tiếp tục sáng tạo với tuyết. Lần này, anh ấy muốn xây dựng một lâu đài tuyết hoành tráng trên một khoảng đất trống. Khu vực đất trống này được chia thành \(N\) ô vuông, ban đầu toàn bộ đều có độ cao là \(0\).

ABNL đã nghĩ ra một thiết kế hoàn hảo cho lâu đài này: một dãy số \(a\) biểu thị chiều cao của từng ô trong lâu đài. ABNL tin rằng nếu mỗi ô đạt đúng chiều cao tương ứng trong dãy \(a\), lâu đài sẽ trở thành tác phẩm tuyết đẹp nhất thế giới từng xây dựng.

Vì không có đủ dụng cụ xây dựng phức tạp, ABNL chỉ có thể sử dụng một xẻng tuyết. Mỗi lần sử dụng xẻng, anh ấy có thể xúc tuyết và rải vào đúng \(K\) ô liên tiếp (có thể rải tràn ra ngoài khu vực nếu cần). Mỗi lần xúc và rải, độ cao của mỗi ô trong \(K\) ô liên tiếp sẽ tăng thêm \(1\) đơn vị.

ABNL đang bận xúc tuyết, do đó hãy giúp ABNL tìm ra cách xây dựng lâu đài với số lần tối thiểu cần sử dụng xẻng tuyết để đạt được chiều cao theo yêu cầu của dãy \(a\). Nếu không thể xây lâu đài với yêu cầu này, hãy báo cho ABNL rằng điều đó là không thể.

Input

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(K\) \((1 \leq K \leq N \leq 2×10^5)\): số ô đất và chiều dài tối đa mà xẻng tuyết có thể rải trong một lần.
• Dòng thứ hai chứa N số nguyên \(a[1], a[2], ..., a[N]\) \((1 \leq a[i] \leq 10^9)\): chiều cao mong muốn của từng ô để hoàn thiện lâu đài.

Output

• In ra số lần tối thiểu cần sử dụng xẻng tuyết nếu có thể xây dựng lâu đài.
• In ra \(-1\) nếu không thể.

Example

5 3
1 1 1 1 2

3

5 3
1 2 3 2 1

3

3 2
1 3 1

-1

5 3
1 1 0 1 1

2