Nhặt sỏi

Trong công viên có $N$ loại sỏi khác nhau; loại thứ $i$ có $w_i$ viên sỏi. Bạn muốn nhặt hết tất cả sỏi và mang về nhà.

Bạn có đúng hai chiếc túi, mỗi túi chứa được tối đa $k$ viên sỏi cùng một lúc. Bạn không bao giờ để chung sỏi thuộc hai loại khác nhau trong cùng một chiếc túi, nhưng hai chiếc túi có thể chứa hai loại sỏi khác nhau tại cùng thời điểm.

Mỗi ngày bạn chỉ được ra công viên nhặt sỏi đúng một lần (tức là mỗi ngày bạn dùng hai chiếc túi để mang về một lượng sỏi). Hãy tìm số ngày ít nhất để nhặt được hết tất cả sỏi.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $k$ — số loại sỏi và sức chứa của mỗi túi.
• Dòng thứ hai chứa $N$ số nguyên $w_1,w_2,\dots ,w_N$ — số viên sỏi của mỗi loại.

Dữ liệu ra

• Một số nguyên duy nhất là số ngày ít nhất cần thiết.

Ràng buộc

• $1\le N\le {10}^5$
• $1\le k\le {10}^9$
• $1\le w_i\le {10}^4$

Ví dụ