Công ty TNHH MTV nước XYZ chuyên sản xuất nước lọc đóng bình. Có N bình đựng nước đặt liên tiếp nhau, được đánh số từ 1 đến N. Mỗi bình có dung tích là ai lít. Tại mỗi bình đều có một vòi nước chảy với lưu lượng giống nhau là K lít/giây. Khi bình thứ i đầy nước (1 ≤ i < N) thì nước từ vòi tại bình i sẽ chảy qua bình i + 1. Khi bình thứ N đầy nước thì nước sẽ chảy ra ngoài.
Yêu cầu:
- Tìm số nguyên tương ứng với thời gian sớm nhất để bình thứ N đầy nước.
- Tìm số nguyên tương ứng với thời gian sớm nhất để tất cả các bình đầy nước.
Lưu ý: chỉ cần tìm ra thời gian nguyên sớm nhất (ví dụ như thời gian tìm được là 1.33 thì kết quả in ra sẽ là 2).
Dữ liệu:
- Dòng đầu tiên chứa số nguyên dương N và K.
- Dòng tiếp theo chứa N số nguyên không âm a1, a2,..., aN.
Kết quả: Ghi ra hai số nguyên không âm lần lượt là thời gian sớm nhất để bình thứ N đầy nước và thời gian sớm nhất để tất cả các bình đầy nước.
Hai số trên cùng một dòng cách nhau một dấu cách.
WATERJUG.INP |
WATERJUG.OUT |
4 2 1 2 3 4 |
2 2 |
4 3 10 7 3 2 |
1 4 |
- Test 01: Kết quả tìm được lần lượt là 1.25 và 1.25 nên in ra hai giá trị nguyên sớm nhất là 2 và 2.
- Test 02, kết quả tìm được lần lượt là 0.6667 và 3.3333 nên in ra hai giá trị nguyên sớm nhất là 1 và 4.
Giới hạn:
* 1 ≤ N ≤ 105.
* 1 ≤ K ≤ 109.
* 1 ≤ ai ≤ 109, với mọi 1 ≤ i ≤ N.