Description

In the lecture before, we've learned how to solve 8 queens problem.

In this problem, you need solve a similar problems. But the girdsize of the board is now n x n rather than 8 x 8. And what you have to place is stars rather than queens. In origin 8 queens problem we know the attacking range of a queen is like the word "米" where the queen is in the center. And the attacking range of a star is like the word "大" where the star is in the center. For example consider n = 8 and place a star at (3, 3), the cells marked O will be attacked by the star.

..O.....

OOSOOOOO

.O.O....

O...O...

.....O..

......O.

.......O

........

 

For each cell (i, j) there is an interger a_ij on it. If you place a star on (i, j), you will score a_ij points.

Your task is to place exactly n stars such that every star would not attacks another star and then maximize the sum of points you score. There may be no placement which meets the condition. Note you can only place at most one star on a cell.

Input

The first line contains one integer n (1 ≤ n ≤ 10) – the side-length of the board.

The following n lines contain n integers each, the j-th element in the i+1-th line is a_ij (-10⁹ ≤ a_ij ≤ 10⁹).

Output

Output the maximum points which meet the condition. If there is no such placement which meets the condition, output "no solution" instead.

And then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are n items. The weight and value of the i-th item are w_i and v_i separately.

The total weight of items you can take away is at most m. What is the maximum sum of value you can get?

Input

The first line contains two integers n, m (1 ≤ n ≤ 20, 1 ≤ m ≤ 1000) – the number of items and the totol weight you can take away.

Then n lines follow. The i+1-th line contains two integers w_i, v_i (1 ≤ w_i ≤ 1000, 1 ≤ v_i ≤ 10⁹) – the weight and value of the i-th item.

Output

Output the maximum sum of value you can get and then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There is a n x m grid. For each cell (i, j) there is exactly a bulb(on or off) on it.

If the bulb on (i, j) is switched(on to off/off to on) by you, all the bulbs on (i-1, j), (i, j-1), (i, j+1) and (i+1, j) will also be switched magically(it the bulb exists).

Now you are give the state of all the bulbs initially. You need to output the minimum number of the bulbs you need to switch such that all the bulbs are on. There may be no such a plan which makes all the bulbs on.

For example, consider a 3 x 3 grid and the bulbs on (1, 3), (3, 2), (3,3) are on in the beginning. The optimal choice to switch the bulbs on (1, 1), (3, 2) and (3, 3).

0 0 1          1 1 1          1 1 1          1 1 1

0 0 0 =======> 1 0 0 =======> 1 1 0 =======> 1 1 1

0 1 1          0 1 1          1 0 0          1 1 1

            switch (1,1)   switch (3,2)   switch (3,3)

 

Input

The first line contains two integers n, m (1 ≤ n x m ≤ 20) – the gridsize of the grid.

The following n lines contain m integers each, the j-th element in the i+1-th line s_ij is state(1 represents on and 0 represents off) of the bulb on (i, j) (0 ≤ s_ij ≤ 1).

Output

Output the minimum number of the bulbs you need to switch such that all the bulbs are on. If there is no such plan which meets the condition, output "no solution" instead.

And then output a newline('\n').

Sample Input  Download

Sample Output  Download

Tags

Discuss