Задача 3. Урюк

Входной файл:apricot.in   Ограничение времени:1 сек
Выходной файл:apricot.out   Ограничение памяти:256 Мб
Максимальный балл:100  

Условие

В давние времена Золотая Орда ежегодно собирала дань золотыми монетами. Известный крымский хан Гирей решил схитрить: выплачивая дань из N золотых монет, он подложил среди них одну фальшивую – более легкую монету. Об этом донесли казначею Золотой Орды. Для обнаружения подделки он решил использовать магические весы, работающие на урюке.

На чаши магических весов кладутся две кучи монет. Весы устанавливают, совпадает или различается вес этих куч. При этом, если кучи имеют разный вес, то весы указывают, какая из куч легче. При совпадении веса обеих куч весы требуют R плодов урюка, а при несовпадении – U плодов.

Казначей, сам любитель урюка, хочет и фальшивую монету обнаружить, и сэкономить на урюке.

Требуется написать программу, которая по заданному количеству монет N, при условии, что только одна из них легче других, укажет минимальное количество урюка, с помощью которого эта фальшивая монета гарантированно будет обнаружена.

Формат входного файла

Во входном файле в единственной строке находятся три целых числа N, R и U, где N – количество монет, R – количество плодов урюка, затрачиваемых в случае совпадения веса куч монет, U – количество плодов урюка, затрачиваемых в случае их различия. Все числа разделены пробелом.

Формат выходного файла

Выходной файл должен содержать одно число – минимальное количество урюка, с помощью которого гарантированно будет обнаружена фальшивая монета.

Ограничения

2 ≤ N ≤ 1 000 000, 1 ≤ R, U ≤ 1 000 000.

Примеры тестов

Входной файл (apricot.in) Выходной файл (apricot.out)
1
4 3 1
2
2
3 3 1
3
3
15 2 3
8
4
10 2 1
3

0.038s 0.007s 15