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?
In the first line you will be given
$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 a single integer, the maximum number of inversion your gift can have.
3 5 011 0 101
If you concatenate the 3rd and the 2nd string, you get 1010, which has 3 inversions: (1, 2), (1, 4), (3, 4).
4 6 10 10 10 0011
If you concatenate 1st, 2nd, 3rd string, you get 101010, which has 6 inversions.