Công ty của gia đình Alice có \(n\) sản phẩm với khối lượng lần lượt là \(a_1, a_2, \dots, a_n\). Công ty sẽ đóng gói thành các kiện hàng để gửi cho khách. Mỗi kiện hàng có đúng \(k\) sản phẩm và khối lượng của các kiện hàng đều bằng nhau. Khối lượng của một kiện hàng bằng tổng khối lượng của \(k\) sản phẩm trong kiện hàng đó. Chú ý là, một sản phẩm thuộc nhiều nhất một kiện hàng.

Alice muốn biết Công ty của gia đình mình có thể đóng gói được nhiều nhất bao nhiêu kiện hàng.

Input

• Dòng đầu tiên ghi hai số nguyên dương \(n, k\) (\(1 \le k \le 3; 1 \le n \le 10^5\)).
• Dòng thứ hai ghi \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 1000\)).

Output

• Gồm một số nguyên là số lượng kiện hàng nhiều nhất có thể đóng gói được.

Example

5 1
1 6 6 4 6

3

5 2
1 6 6 4 6

1

10 3
1 2 3 3 2 2 2 1 1 1

3

Scoring

• Subtask \(1\) (\(40\%\) số điểm): Ứng với \(k = 1, n \le 1000\).
• Subtask \(2\) (\(40\%\) số điểm): Ứng với \(k = 2\).
• Subtask \(3\) (\(20\%\) số điểm): Ứng với \(k = 3, 1 \le a_i \le 3\).