Algorithm Implementation

  algorithm, arrays, java, optimization, python

Arnab placed a box (shape of a cube of side
1
meter). The box was placed in the corner of a rectangular room measuring
m

n
. The word "SECRET" was written on its upper edge in red paint.

Today, Arnab suddenly needed to move this box to the opposite corner of the room. But, unfortunately, the box turned out to be so heavy that no one could move it. It turned out that all that can be done with the box is to roll it over the edge of the bottom face. The corresponding edge remains in the same place and another face adjacent to this edge becomes the lower one.

Arnab needs to roll the box from the corner of the room in which it stands, to the opposite corner. At the same time, even rolling the box is very difficult, so Arnab decided to minimize the number of rolling the box.

But when Arnab was about to start transporting, another problem came to light. The red inscription "SECRET" every time, touching the floor, leaves traces on it. Therefore, among all the transportation options that minimize the number of rolls, Arnab decided to choose the one in which the inscription "SECRET" appears on the bottom edge of the cube the minimum number of times.

Help Arnab count how many times the inscription "SECRET" will touch the floor with the optimal rolling of the cube.

Input

m and n i.e room size

Output format

Print one number how many times the inscription "SECRET" will appear on the bottom edge when the box is moved optimally.

Time

1 seconds

Example

Input

3 3

Output

1

Explanation

In the example, four rolls are required. In any case, the inscription "SECRET" will touch the floor at least once.
One way to make rolling so that it happens once is the next. First, roll the cube twice in one direction (it will be in the next corner of the room).
Now the inscription "SECRET" is on the lower edge and touches the floor. Then we roll the cube two more times in the perpendicular direction. The cube is now in the desired position.

Source: Python Questions

One Reply to “Algorithm Implementation”

LEAVE A COMMENT