THỰC HÀNH

(Đề đề xuất DHBB 2017 của THPT CHUYÊN QUỐC HỌC HUẾ)

Cho một đàn kiến gồm n con đang đi trên một sợi dây căng ngang có hai đầu là A và B chiều dài k cm. Trong đàn có số con kiến đi về phía điểm A, những con còn lại đi về phía điểm B, ban đầu không có hai con nào ở cùng vị trí.

Các con kiến đều di chuyển với tốc độ giống nhau: 1 cm/s, khi hai con kiến gặp nhau, chúng chạm râu vào nhau rồi cùng quay lại để di chuyển theo hướng ngược lại. Khi một con kiến chạm vào điểm A hay điểm B, nó sẽ bị rơi xuống đất và không còn trên dây nữa.

Yêu cầu: Biết vị trí và hướng di chuyển của từng con kiến tại thời điểm xuất phát là thời điểm 0, tính thời điểm chú kiến cuối cùng bị rơi xuống đất

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương n và k.
• Dòng thứ hai chứa n số nguyên x₁, x₂, …, x_n trong đó |x_i| là khoảng cách từ chú kiến thứ i tới điểm A, x_i < 0 có nghĩa là ban đầu chú kiến thứ i di chuyển về phía điểm A, x_i > 0 có nghĩa là ban đầu chú kiến thứ i di chuyển về phía điểm B.

Các số liên tiếp trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Dữ liệu ra:

            Ghi trên một dòng một số nguyên duy nhất là thời điểm chú kiến cuối cùng bị rơi xuống đất.

Ví dụ:

Dữ liệu vào:
2 6
1 -5
Dữ liệu ra:
5

Giới hạn: 1 ≤ N ≤ 10⁵; 1 ≤ k ≤ 10¹⁸; 1 ≤ |x_i| < k.