CF1530B Putting Plates

To celebrate your birthday you have prepared a festive table! Now you want to seat as many guests as possible. The table can be represented as a rectangle with height $ h $ and width $ w $ , divided into $ h \times w $ cells. Let $ (i, j) $ denote the cell in the $ i $ -th row and the $ j $ -th column of the rectangle ( $ 1 \le i \le h $ ; $ 1 \le j \le w $ ). Into each cell of the table you can either put a plate or keep it empty. As each guest has to be seated next to their plate, you can only put plates on the edge of the table — into the first or the last row of the rectangle, or into the first or the last column. Formally, for each cell $ (i, j) $ you put a plate into, at least one of the following conditions must be satisfied: $ i = 1 $ , $ i = h $ , $ j = 1 $ , $ j = w $ . To make the guests comfortable, no two plates must be put into cells that have a common side or corner. In other words, if cell $ (i, j) $ contains a plate, you can't put plates into cells $ (i - 1, j) $ , $ (i, j - 1) $ , $ (i + 1, j) $ , $ (i, j + 1) $ , $ (i - 1, j - 1) $ , $ (i - 1, j + 1) $ , $ (i + 1, j - 1) $ , $ (i + 1, j + 1) $ . Put as many plates on the table as possible without violating the rules above.

N/A

N/A

For the first test case, example output contains the only way to put $ 6 $ plates on the table. For the second test case, there are many ways to put $ 4 $ plates on the table, example output contains one of them. Putting more than $ 6 $ plates in the first test case or more than $ 4 $ plates in the second test case is impossible.