The game works as follows. Your parents place a $p \times q$-rectangle of the aforementioned mixed chocolate on a table. You are situated on the west side of the table and your sister on the south side. The side of length $p$ is parallel to the north-south line, while the side of length $q$ is parallel to the east-west line. Furthermore, the north-west square is made of dark chocolate. Then, starting with yourself, you take turns breaking off blocks of chocolate (which you can keep). You can break off any positive number of entire columns from the west side, while your sister breaks off any positive number of entire rows from the south side. You repeat this process until no more chocolate is left. Your sister is very smart and will always play the game perfectly.
A game might proceed like this, for example: you and your sister start with a $3\times 4$-rectangle. You decide to break off $2$ columns, obtaining $3$ dark and $3$ white chocolate squares, netting a happiness of zero. Your sister then breaks off $1$ row, obtaining $1$ dark and $1$ white squares as well, so no happiness for her either. You then take a single column, which nets you nothing again, after which your sister decides to break off one row, which nets her $1$ happiness! You then take the last piece, which makes you lose a unit of happiness, so your total score is $-1 - 1 = -2$. See the figure. (Note: the strategies used here might not be optimal.)
Given are two positive integers $p$ and $q$, both at most $100$, the height and width of the chocolate rectangle.
Output the largest possible difference (in your favour) between your net happiness and your sisterâ€™s net happiness.
Sample Input 1 | Sample Output 1 |
---|---|
1 2 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
2 2 |
0 |
Sample Input 3 | Sample Output 3 |
---|---|
4 3 |
0 |