← 返回题目列表

Codeforces · 1214/A

A. 最佳货币兑换

中文机器翻译题面 查看原题

安德鲁非常高兴能够参加城市奥林匹克运动会。日子过得很快,安德鲁已经到了机场,准备回家。他还剩下 $$$n$$$ 卢布,想将其兑换成欧元和美元。安德鲁可以以任何他想要的方式混合美元钞票和欧元钞票。一美元的价格为 $$$d$$$ 卢布,一欧元的价格为 $$$e$$$ 卢布。

回想一下,存在以下美元钞票:$$$1$$$、$$$2$$$、$$$5$$$、$$$10$$$、$$$20$$$、$$$50$$$、$$$100$$$ 以及以下欧元钞票 — $$$5$$$、$$$10$$$、$$$20$$$、 $$$50$$$、$$$100$$$、$$$200$$$(注意,在这个问题中我们不考虑$$$500$$$欧元纸币,在货币兑换点很难找到这样的纸币)。安德鲁可以购买任意纸币组合,他的目标是尽量减少兑换后拥有的卢布总数。

帮助他——编写一个程序,给定整数 $$$n$$$、$$$e$$$ 和 $$$d$$$,找出安德鲁在购买美元和欧元钞票后可以获得的最少卢布数量。

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^8$$$) - Andrew 的卢布初始总和。

输入的第二行包含一个整数 $$$d$$$ ($$$30 \leq d \leq 100$$$) — 一美元卢布的价格。

输入的第三行包含整数 $$$e$$$ ($$$30 \leq e \leq 100$$$) — 一欧元卢布的价格。

输出

输出一个整数——安德鲁在最佳购买美元和欧元钞票后可以拥有的最少卢布数量。

示例

输入 #1

100
60
70

输出 #1

40

输入 #2

410
55
70

输出 #2

5

输入 #3

600
60
70

输出 #3

0

注意

在第一个示例中,我们只能购买 $$$1$$$ 美元,因为没有 $$$1$$$ 欧元纸币。

在第二个示例中,最佳兑换是购买 $$$5$$$ 欧元和 $$$1$$$ 美元。

在第三个示例中,最佳兑换是在一张钞票中购买 $$$10$$$ 美元。