F. Crazy Thursday, V me 50!
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

BSQ has $$$n$$$ QQ groups, and each group consists of some rich guys. BSQ can send a mystery message to these groups to get some money. The rules are the following:

  • BSQ can send "Crazy Thursday, V me 50!" to some group he has not sent the message to before.
  • Once BSQ sends the message to some group, the rich guys in this group will give him some money one by one in the lexicographical order of their name.
  • Each rich guy will give BSQ money as much as possible, but they must meet two constraints: Each guy will give BSQ at most $$$50$$$ in total (NOT in a single group), and BSQ can get at most $$$114$$$ in one group.
  • One rich guy can be in several groups. Every rich guy has a unique name consisting of lowercase letters. No two same names will be in the same group.

Now BSQ has decided to send messages to exactly $$$k$$$ different groups. He can decide the order of groups to send the message to. What is the maximum amount of money he can get?

Lexicographical order is defined in the following way. When we compare $$$s$$$ and $$$t$$$, first, we find the leftmost position with differing characters: $$$s_i \ne t_i$$$. If there is no such position (i. e. $$$s$$$ is a prefix of $$$t$$$ or vice versa), the shorter string is less. Otherwise, we compare characters $$$s_i$$$ and $$$t_i$$$ according to their order in the alphabet.

Input

The first line contains two integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le n \le 8)$$$ — the number of groups and groups BSQ will send a message to.

Then $$$n$$$ lines follow, each starting with an integer $$$m$$$ $$$(1 \le m \le 10)$$$, the number of rich guys in this group. Following $$$m$$$ strings, the names of the rich guys. The length of each name will not exceed $$$10$$$. It is NOT guaranteed that the names have been sorted.

Output

Print a single integer in a line — the maximum amount BSQ can get.

Examples
Input
2 2
3 alice boboge cityu
3 ddddc faker euler
Output
228
Input
2 2
4 alice boboge cityu ddddc
1 alice
Output
164
Input
3 2
1 zawei
3 hile zawei meow
3 meow zawei hile
Output
150
Note

For the first sample, BSQ gets $$$114$$$ in both groups, $$$228$$$ in total.

For the second sample, BSQ first sends a message to the second group so that alice will give him $$$50$$$, and then other people in the first group will give him $$$114$$$. If BSQ starts with the first group, he will only get $$$114$$$ because alice has already given him $$$50$$$ in the first group.