Inversions and Goodbye

It's time to say goodbye to CSEmpur, at least for today. And so you wanted to give the citizens of CSEmpur a parting gift. However since you are broke, you are trying to make some gift for them. You have n binary strings. You want to concatenate some of these strings so that their length is at most k (too large strings are heavy, and you really don't want to carry heavy gifts).

Now you know that, CSEmpurians like inversions in binary strings. An inversion is any pair of indices (i, j) such that i < j and si > sj. So for example in string '1001', the (1, 2) and (1, 3) pairs are inversions.

So you have an optimization problem ahead of you (a scenario too common in Computer Science), What is the maximum number of inversions your gift can have while being at most k characters long?

Input

In the first line you will be given $n$ and $k$, the number of binary strings you have. The next n lines will each contain a binary string (string consisting of 1 and 0).

1 ≤ n ≤ 500
1 ≤ k ≤ sum of length of all input strings ≤ 500

Output

Output a single integer, the maximum number of inversion your gift can have.

Samples

3 5
011
0
101

3

4 6
10
10
10
0011

6