Given an n × m chess board, how many knights can we place on it so that no two knights threaten each other? For instance, we can place six knights on a 2 × 5 board:

boardfontsize=24pt
showmover=false,
label=false,
maxfield=e2,
setpieces=na1,na2,nb2,nd2,ne2,ne1

Input

Input consists of several cases, each with n and m,
both between 1 and 10^{4}.

Output

For every case, print the maximum number of knights that we can place on an n × m chess board without any threats.

Public test cases

**Input**

2 5 1 1 4 1 3 5

**Output**

6 1 4 8

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++