Background

Special for beginners, ^_^

Description

给定一个 n 行 32 列的方格图，每一个格子里都写有一个数字 0/1 ，每行的积分为将该行从左至右所连成的二进制数。

一次左移变换是指把某一行所有的数都左移一格，同时将那一行的第 1 个数移到该行的最后一格。

在不超过 m 次左移变换后， n 行的积分和 S 最大能是多少。

Format

Input

第一行包含两个正整数 n 和 m （$n, m \le1000$），用一个空格分隔。

接下来 n 行，每行包含一个正整数，表示初始积分在十进制下的数。

Output

一个整数，表示 n 行的积分和 S 的最大值。

Samples

3 9
2365587456
2399141888
9437184

7535067152

Limitation

1s, 1024KiB for each test case.