C11PINES - Growing Pines

Giới hạn
  • Thời gian: 1.0s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

 

yenthanh132 có một vườn thông, vườn thông bao gồm N cây thông xếp theo một đường thẳng. Do được trồng ở khu đất màu mỡ nên các cây thông của anh ta lớn rất nhanh, mỗi ngày mỗi cây thông sẽ tăng thêm d cm chiều cao.

Pines

Giáng sinh sắp tới rồi nên yenthanh132 muốn làm đẹp lại khu vườn của mình, anh ta muốn N cây thông sẽ có chiều cao như nhau, để làm được điều đó anh ta có một loại thuốc ngăn chặn sự phát triển của cây thông, mỗi lần phun thuốc cho 1 cây thông thuốc sẽ có tác dụng làm cho cây thông giữ nguyên chiều cao trong vòng 1 ngày, do thời gian có hạn nên mỗi ngày yenthanh132 chỉ có thể chọn một cây thông trong N cây thông để phun loại thuốc đó, cây thông bị phun thuốc sẽ giữ nguyên chiều cao trong suốt ngày hôm ấy và N-1 cây thông còn lại mỗi cây sẽ tăng thêm d cm chiều cao như bình thường.

Hãy giúp yenthanh132 sắp xếp lịch phun thuốc để N cây thông có chiều cao bằng nhau sau ít ngày nhất. Hoặc nói với yenthanh132 rằng anh ta không thể làm cho N cây thông có chiều cao bằng nhau được.

Input

  • Dòng đầu gồm 2 số nguyên dương: N, d ; mỗi số cách nhau 1 dấu cách
  • Dòng tiếp theo có N số nguyên dương, số thứ i là chiều cao của cây thông thứ i.

Output

  • In ra một số nguyên duy nhất là số ngày ít nhất để N cây thông của yenthanh132 có chiều cao như nhau. Trường hợp không thể làm N cây thông có chiều cao như nhau được thì in ra -1

Giới hạn

  • 1 <= d <= 10.
  • Chiều cao của cây thông là 1 số nguyên trong đoạn [1, 10 9 ]
  • Trong 20% test đầu có N <= 100.
  • Trong 20% test tiếp theo có N <= 1000.
  • Trong tất cả các test có N <= 10000.

Example

Input:
3 2
1 5 3

Output:
3
Giải thích: Có cách để sau 3 ngày 3 cây thông sẽ có chiều cao như nhau:
- Ngày 1: Phun thuốc vào cây thông thứ 2, chiều cao của 3 cây sau ngày 1 là: 3 5 5
- Ngày 2: Phun thuốc vào cây thông thứ 3, chiều cao của 3 cây sau ngày 2 là: 5 7 5
- Ngày 3: Phun thuốc vào cây thông thứ 2, chiều cao của 3 cây sau ngày 3 là: 7 7 7.
Vậy sau 3 ngày chiều cao của 3 cây thông đã bằng nhau

  • Người up: yenthanh132
  • Nguồn bài: VOS Round 23 - Lê Yên Thanh