ropes

Anh Vinh có n đoạn dây thừng có độ dài lần lượt là a0, a1, ..., an-1.

Anh Vinh đang cần k đoạn dây thừng có độ dài bằng nhau, nên anh Vinh quyết định sẽ cắt n đoạn dây đó để có được k đoạn dây bằng nhau, mỗi đoạn có độ dài là một số nguyên dương x.

Hãy tìm và đưa ra độ dài x lớn nhất có thể của k đoạn dây sau khi cắt. Nếu không tồn tại cách cắt nào để anh Vinh có k đoạn dây bằng nhau thì đưa ra -1.

Ví dụ:

• Với a = [803,456,723,231], k = 10, thì ropes(a,k) = 200.
  
  Giải thích: Anh vĩnh có 4 đoạn dây có độ dài là 803, 456, 723, 231, và anh Vinh cần 10 đoạn dây bằng nhau.
  Độ dài lớn nhất của 10 đoạn dây đó là 200.
  • Với đoạn dây có độ dài 803, ta có thể cắt được 4 đoạn dây độ dài 200.
  • Với đoạn dây có độ dài 456, ta có thể cắt được 2 đoạn dây độ dài 200.
  • Với đoạn dây có độ dài 723, ta có thể cắt được 3 đoạn dây độ dài 200.
  • Với đoạn dây có độ dài 231, ta có thể cắt được 1 đoạn dây độ dài 200.
• Với a = [1,1,2], k = 5, thì ropes(a,k) = -1.

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript

• [Đầu vào] Array of integer a
  1 ≤ a.size ≤ 106.
1 ≤ a[i] ≤ 103.
• [Đầu vào] Integer k
  1 ≤ k ≤ 109.
• [Đầu ra] Integer
  Số nguyên dương x lớn nhất là độ dài của k đoạn dây. Nếu không tồn tại cách cắt nào để có k đoạn day bằng nhau thì trả về -1.