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.

Scoring

Sample Input 1

5 1
1 6 6 4 6

Sample Output 1

3

Sample Input 2

5 2
1 6 6 4 6

Sample Output 2

1

Sample Input 3

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

Sample Output 3

3

Notes

Trong ví dụ thứ nhất, đóng gói được nhiều nhất ~3~ kiện hàng, mỗi kiện hàng gồm ~1~ sản phẩm. Đó là các sản phẩm thứ ~2,3,5~. Các sản phẩm này đều có khối lượng bằng ~6~.

Trong ví dụ thứ hai, đóng gói được nhiều nhất một kiện hàng gồm ~2~ sản phẩm. Có thể lấy hai sản phẩm bất kì để đóng gói thành ~1~ kiện hàng.

Trong ví dụ thứ ba, đóng gói được nhiều nhất ~3~ kiện hàng, mỗi kiện hàng gồm ~3~ sản phẩm. Cụ thể, ~3~ kiện hàng, mỗi kiện hàng gồm ~3~ sản phẩm có khối lượng như sau:

• ~\{1,2,2\} \rightarrow~ tổng khối lượng bằng ~5~.

• ~\{1,2,2\} \rightarrow~ tổng khối lượng bằng ~5~.

• ~\{1,1,3\} \rightarrow~ tổng khối lượng bằng ~5~.