Оказывается, шахматные кони не очень любят ходить друг к другу в гости. Обычно дорога проходит окольными путями. Прийти с подарком тоже не получится, ведь его негде взять. А если гости всё-таки пришли, то они занимают собой весь дом, и владельцу нужно куда-то уйти на то время, пока в его доме гости.

Недавно конь Остап задался вопросом переезда на другую доску размером N × N. Переезжать одному ему не хочется, поэтому он хочет найти как можно больше единомышленников. Единственная причина переезда в том, что сейчас к нему постоянно приходят гости, поэтому, чтобы такое не повторялось, ему хочется узнать максимальное количество единомышленников, которые поместятся на новой доске так, что никто не сможет ходить друг к другу в гости.

Дом каждого коня находится в одной из клеток. Один конь может сходить в гости к другому, если существует путь, состоящий из произвольного количества ходов коней, который идёт из дома первого коня в дом второго. Известно, что кони передвигаются только буквой «Г»: сначала на B клеток вперед, а затем на A клеток в сторону.

Вот так выглядят все варианты одного хода шахматного коня при A = 1, B = 2:

В первой строке указывается размер доски N (1 ≤ N ≤ 10⁹). Во второй и третьей строках указываются параметры ходов коней — A и B (0 ≤ A ≤ B ≤ 3).

В единственной строке выведите, сколько коней может переехать на новую доску. В это количество должен входить Остап.