Sick Knight

Time limit2sMemory limit128 MB

Summary

Given an N by M board, find the max cells a knight limited to four specific diagonal jumps can visit, using all four move types once it makes 4+ moves.

Level: Medium6 of 10
Topics: Math, Greedy, Implementation
Solved: No attempts yet

Problem

A sick knight stands on the bottom-left cell of an N x M chessboard. Unlike an ordinary knight, it can move only in the following four ways.

2 cells up and 1 cell right
1 cell up and 2 cells right
1 cell down and 2 cells right
2 cells down and 1 cell right

The knight wants to travel while maximizing the number of cells it visits. However, if it makes at least 4 moves, it must use each of the four move types at least once. If it makes at most 3 moves, there is no additional restriction on the move types.

Given N and M, find the maximum number of cells the knight can visit.

Input

The first line contains the chessboard height N and width M. Both N and M are positive integers not greater than 2,000,000,000.

Output

Print the maximum number of cells the knight can visit during its trip.

Examples5

Example 1
Input
```
100 50
```
Expected output
```
48
```
Example 2
Input
```
1 1
```
Expected output
```
1
```
Example 3
Input
```
17 5
```
Expected output
```
4
```
Example 4
Input
```
2 4
```
Expected output
```
2
```
Example 5
Input
```
20 4
```
Expected output
```
4
```