Dạo gần đây, Phúc mới dần được học cách sử dụng các câu lệnh terminal để quản lý máy tính một cách hiệu quả hơn. Hào hứng trước những kiến thức mới, Phúc rất mong muốn được mau chóng áp dụng chúng vào thực tiễn, trước mắt là trong việc dọn dẹp các tập tin lộn xộn trên máy tính của mình.

Phúc muốn xóa ~n~ file trên máy tính của mình, tuy nhiên vì số lượng file quá lớn nên việc dọn dẹp thủ công đối với Phúc dường như là không thể vì Phúc lười. May mắn thay, trong các câu lệnh terminal Phúc vừa học có câu lệnh rm [tiền tố]* có thể giúp Phúc xóa đồng loạt tất cả các file có tên nhận *[tiền tố] làm tiền tố của nó.*

Tuy nhiên, để đảm bảo an ninh dữ liệu trên máy tính (tránh việc người dùng xóa quá nhiều file dẫn đến mất thông tin), các nhà sản xuất khi cài đặt đã giới hạn mỗi lần máy tính sử dụng câu lệnh trên chỉ được xóa tối đa ~k~ file cùng lúc. Chính vì thế, Phúc cần phải tính toán hợp lý mình cần gõ những câu lệnh nào để vừa có thể dọn dẹp một cách hiệu quả vừa không phải tốn sức gõ quá nhiều lệnh.

Các bạn hãy giúp Phúc tính xem Phúc cần gõ ít nhất bao nhiêu lần dòng lệnh rm trên để dọn dẹp máy tính của mình nhé!

Input

Dòng đầu tiên chứa ~2~ số nguyên dương ~n~, ~k~ ~(1 \le n, k \le 3 \cdot 10^5)~ - số lượng file trong máy tính của Phúc cần xóa và số lượng file tối đa một lần máy của Phúc có thể xóa được.

~n~ dòng tiếp theo, mỗi dòng gồm ~1~ xâu ~s~ ~(1 \le |s| \le 3 \cdot 10^5)~ là tên của các file trong máy tính của Phúc cần được dọn dẹp.

Biết rằng tên của tất cả các file trong máy tính của Phúc đều chỉ gồm các chữ cái in thường a-z, đôi một khác nhau, và tổng độ dài tên của tất cả các file không vượt quá ~3 \cdot 10^5~.

Output

Gồm ~1~ số nguyên dương duy nhất là số lần tối thiểu Phúc cần thực hiện lệnh để dọn dẹp hết toàn bộ file cần xóa trong máy.

Scoring

• ~10\%~ số test có ~k=1~.

• ~30\%~ số test có ~\sum |s| \le 5000~.

• ~60\%~ số test còn lại không có giới hạn gì thêm.

Sample Input 1

4 2
a
abc
abd
b

Sample Output 1

2

Sample Input 2

4 2
d
c
ab
a

Sample Output 2

2

Sample Input 3

5 3
please
remove
all
these
files

Sample Output 3

3