No.176 2種類の切手

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 97
作問者 : tailstails

8 ProblemId : 457 / 出題時の順位表

問題文

Yuki王国では、$A$円と$B$円の2種類の郵便切手が発行されています。

あなたは、これら2種類の切手をうまく組み合わせて、
郵便物に$T$円分以上の切手を貼ろうとしていますが、
切手の合計額がなるべく少なくなるようにしなければなりません。

切手の合計額が最も少なくなるようにしたとき、
何円分の切手を貼ることになるでしょうか?
その合計額を答えてください。

なお、必ずしも両方の種類の切手を使う必要はなく、
切手の枚数に制限はありません。

入力

$A$ $B$ $T$

$1 \le A < B \le 10^9$
$1 \le T \le 10^9$
$A$, $B$, $T$ はいずれも整数です。

出力

切手の合計額を出力してください。

サンプル

サンプル1
入力
50 80 120
出力
130

50円切手と80円切手を組み合わせて、ちょうど120円にすることはできません。
この場合、50円切手と80円切手を1枚ずつ使って130円にするのが、
120円以上での最少額になります。

サンプル2
入力
123 456 1
出力
123

必ずしも両方の種類の切手を使う必要はありません。
この場合、額面の小さい123円の切手を1枚貼ることになります。

サンプル3
入力
1234 1688 10000
出力
10000

うまくすれば、ちょうど10000円にできるようです。

提出ページヘ