It turns out, chess knights don’t really like to visit each other. Usually, the road goes roundabout ways. Coming with present is also not an option, because there is nowhere to get a present from.
And if guests finally come, they occupy all the space, and the host has to leave the house until the guests quit.
Not so long ago knight Ostap started to consider an option of moving to another chessboard of size N × N. He doesn’t want to move alone. Instead, he wants to invite as many other knights as possible to join him. The only reason for moving is the fact that right now he has guests all the time. In order to not repeat his mistake, he wants to know the maximum number of knights he can invite with him, such that they will all fit in the new chessboard and no one will be able to visit anyone else.
The house of every knight is located in some cell of a chessboard. A knight can visit another knight, if there is a path between their houses, consisting of knight moves. It is known that knights only move in the following way: at first B cells forward, then A cells sideward.
This is how all the possible moves of a knight look like for A = 1, B = 2:
The first line contains the size of the chessboard N (1 ≤ N ≤ 109). The second and the third lines contain the parameters of the knight move — A and B (0 ≤ A ≤ B ≤ 3).
In a single line you should output the maximum number of knights that can move to a new chessboard. Ostap should be included in this number.
Problem Author: Kirill Deviatkin
Problem Source: University academic school olympiad in informatics 2019