404994: GYM101727 F Lying Processors

To test the most recent advances in algorithms of machine learning Evgeny uses n·m processors that are arranged in unit cells of n × m board. Thus, processors occupy n rows, each containing m of them. Two processors are called neighbors if they are arranged in neighboring cells of one row, or at the same positions in neighboring rows.

As a result of an unsuccessful experiment with a new algorithm some processors learned to lie to Evgeny. However, thanks to the base version of algorithm that was used, all the processors that learned to lie, do so every time they report something to Evgeny, so the result of their work is still ease to interpret.

Now Evgeny is working to determine which of the processors always say lie, but to start with he wants to understand the possible size of the problem. To make this he asked each of the processors whether it is true that among its neighbors there are processors that work correct and processor that always return lie? To his surprise, each of the processors answered positive. Now Evgeny wonders, what is the minimum possible number of lying processors on the board that can result such answers?

The only line of the input contains two integers n and m (1 ≤ n ≤ 7, 1 ≤ m ≤ 100) — the number of rows on the board and the number of processors in each of the rows respectively.

Print one integer — the minimum possible number of liars among the processors on the board, that could result that each of the processors reported that among its neighbors there are both correct and lying processors.

2 3

2

6 6

10

One of the possible solutions in the first sample is (liars are marked as 1's): 1):

100
001