시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 395 46 31 20.667%

문제

상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 N개를 선물하려고 한다. 상근이네 집 근처에 꽃집의 수는 두 개이다. 두 꽃 집은 발렌타인 대이를 대비해 많은 꽃을 준비했기 때문에, 꽃이 부족한 일은 없다. 하지만, 두 곳 모두 장미를 다발로 묶어서 판다.

첫 번째 꽃집은 장미 A개를 B원에 팔고, 두 번째 꽃집은 C개를 D원에 판다. A, B, C, D는 모두 양의 정수이다. 만약, 장미 N개를 보다 많이 구매하는 것이 정확하게 N개를 구매하는 것 보다 가격이 저렴하면, N개 보다 많이 구매한 다음 남은 장미는 꽃집 점원에게 줄 것이다.

상근이가 장미를 적어도 N개 구매하는데 필요한 최소 금액을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, A, B, C, D가 주어진다. N은 1015를 넘지 않으며, A, B, C, D는 105를 넘지 않는다.

출력

첫째 줄에 장미를 적어도 N개 사는데 필요한 돈의 최솟값을 출력한다. 정답은 항상 1018을 넘지 않는다.

예제 입력 1

22 2 3 10 14

예제 출력 1

31

힌트

첫 번째 꽃 집에서 꽃 다발 1개, 두 번째 꽃 집에서 2개를 구매한다.

W3sicHJvYmxlbV9pZCI6IjMzNDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWJiZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWJjMWNcdWI4MGNcdWQwYzBcdWM3NzggXHViMzcwXHVjNzc0XHViOTdjIFx1YWUzMFx1YjE1MFx1ZDU3NCBcdWM1ZWNcdWM3OTBcdWNlNWNcdWFkNmNcdWM1ZDBcdWFjOGMgXHViMTc4XHViNzgwIFx1YzdhNVx1YmJmOCBOXHVhYzFjXHViOTdjIFx1YzEyMFx1YmIzY1x1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjEyNCBcdWM5ZDEgXHVhZGZjXHVjYzk4XHVjNWQwIFx1YWY0M1x1YzlkMVx1Yzc1OCBcdWMyMThcdWIyOTQgXHViNDUwIFx1YWMxY1x1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YWY0MyBcdWM5ZDFcdWM3NDAgXHViYzFjXHViODBjXHVkMGMwXHVjNzc4IFx1YjMwMFx1Yzc3NFx1Yjk3YyBcdWIzMDBcdWJlNDRcdWQ1NzQgXHViOWNlXHVjNzQwIFx1YWY0M1x1Yzc0NCBcdWM5MDBcdWJlNDRcdWQ1ODhcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWFmNDNcdWM3NzQgXHViZDgwXHVjODcxXHVkNTVjIFx1Yzc3Y1x1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHViNDUwIFx1YWNmMyBcdWJhYThcdWI0NTAgXHVjN2E1XHViYmY4XHViOTdjIFx1YjJlNFx1YmMxY1x1Yjg1YyBcdWJiMzZcdWM1YjRcdWMxMWMgXHVkMzEwXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YWY0M1x1YzlkMVx1Yzc0MCBcdWM3YTVcdWJiZjggQVx1YWMxY1x1Yjk3YyBCXHVjNmQwXHVjNWQwIFx1ZDMxNFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWFmNDNcdWM5ZDFcdWM3NDAgQ1x1YWMxY1x1Yjk3YyBEXHVjNmQwXHVjNWQwIFx1ZDMxMFx1YjJlNC4gQSwgQiwgQywgRFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNTkxXHVjNzU4IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWM3YTVcdWJiZjggTlx1YWMxY1x1Yjk3YyBcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzc0IFx1YWQ2Y1x1YjllNFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzQgXHVjODE1XHVkNjU1XHVkNTU4XHVhYzhjIE5cdWFjMWNcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTU4XHViMjk0IFx1YWM4MyBcdWJjZjRcdWIyZTQgXHVhYzAwXHVhY2E5XHVjNzc0IFx1YzgwMFx1YjgzNFx1ZDU1OFx1YmE3NCwgTlx1YWMxYyBcdWJjZjRcdWIyZTQgXHViOWNlXHVjNzc0IFx1YWQ2Y1x1YjllNFx1ZDU1YyBcdWIyZTRcdWM3NGMgXHViMGE4XHVjNzQwIFx1YzdhNVx1YmJmOFx1YjI5NCBcdWFmNDNcdWM5ZDEgXHVjODEwXHVjNmQwXHVjNWQwXHVhYzhjIFx1YzkwNCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3YTVcdWJiZjhcdWI5N2MgXHVjODAxXHVjNWI0XHViM2M0IE5cdWFjMWMgXHVhZDZjXHViOWU0XHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHVhZTA4XHVjNTYxXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOLCBBLCBCLCBDLCBEXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gTlx1Yzc0MCAxMDxzdXA+MTU8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzAsIEEsIEIsIEMsIERcdWIyOTQgMTA8c3VwPjU8XC9zdXA+XHViOTdjIFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM3YTVcdWJiZjhcdWI5N2MgXHVjODAxXHVjNWI0XHViM2M0IE5cdWFjMWMgXHVjMGFjXHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWIzYzhcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzQwIFx1ZDU2ZFx1YzBjMSAxMDxzdXA+MTg8XC9zdXA+XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZjQzIFx1YzlkMVx1YzVkMFx1YzExYyBcdWFmNDMgXHViMmU0XHViYzFjIDFcdWFjMWMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhZjQzIFx1YzlkMVx1YzVkMFx1YzExYyAyXHVhYzFjXHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzM0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJvc2VzIiwiZGVzY3JpcHRpb24iOiI8cD5WYWxlbnRpbmUgaGFzIGRlY2lkZWQgdG8gY29uZ3JhdHVsYXRlIGFsbCBvZiBoaXMgTiBnaXJsZnJpZW5kcyBieSBnaXZpbmcgZWFjaCBvbmUgYSB5ZWxsb3cgcm9zZS4gSW4gdGhlIG5lYXJieSBmbG93ZXIgbWFya2V0IHllbGxvdyByb3NlcyBhcmUgc29sZCBieSBleGFjdGx5IHR3byB2ZW5kb3JzLiBFYWNoIG9mIHRoZW0gaGFzIGFuIHVubGltaXRlZCBhbW91bnQgb2Ygcm9zZXM7IGhvd2V2ZXIsIHRoZXkgc2VsbCByb3NlcyBvbmx5IGluIGJvdXF1ZXRzIChzbyB5b3UgY2FuIG9ubHkgYnV5IGEgY2VydGFpbiBhbW91bnQgb2Ygcm9zZXMgYXQgYSB0aW1lKS4gQXQgdGhlIGZpcnN0IHZlbmRvciB5b3UgY2FuIGJ1eSBhIGJvdXF1ZXQgb2YgQSByb3NlcyBmb3IgQiBFdXJvczsgYXQgdGhlIHNlY29uZCB2ZW5kb3IgJm5kYXNoOyBhIGJvdXF1ZXQgb2YgQyByb3NlcyBmb3IgRCBFdXJvcy4gQSwgQiwgQywgYW5kIEQgYXJlIGFsbCBwb3NpdGl2ZSBpbnRlZ2Vycy4gSWYgVmFsZW50aW5lIGNhbiBidXkgbW9yZSB0aGFuIE4gcm9zZXMgZm9yIGEgc21hbGxlciBhbW91bnQgb2YgbW9uZXkgdGhhbiBidXlpbmcgcHJlY2lzZWx5IE4gcm9zZXMsIGhlIHdpbGwgYnV5IG1vcmUgdGhhbiBOIHJvc2VzIGFuZCBnaWZ0IHRoZSBsZWZ0b3ZlciB0byBhbnkgb2YgdGhlIHR3byBsb3ZlbHkgJm5ic3A7c2FsZXNnaXJscy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbWluaW11bSBhbW91bnQgb2YgbW9uZXkgaW4gRXVyb3MgZm9yIHdoaWNoIFZhbGVudGluZSBjYW4gYnV5IGF0IGxlYXN0IE4gcm9zZXMhJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgZXhhY3RseSBvbmUgbGluZS4gVGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgY29udGFpbnMgZml2ZSBpbnRlZ2VyczogTiwgQSwgQiwgQywgYW5kIEQ7IGV2ZXJ5IHR3byBjb25zZWN1dGl2ZSBudW1iZXJzIGFyZSBzZXBhcmF0ZWQgYnkgYSBzaW5nbGUgd2hpdGVzcGFjZS4gVGhlIHZhbHVlIG9mIE4gZG9lcyBub3QgZXhjZWVkIDEwPHN1cD4xNTxcL3N1cD4sIHRoZSB2YWx1ZXMgb2YgQSwgQiwgQywgYW5kIEQgZG8gbm90IGV4Y2VlZCAxMDxzdXA+NTxcL3N1cD4uJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIG91dHB1dCBzaG91bGQgY29udGFpbiBvbmUgbGluZSB3aXRoIG9uZSBuYXR1cmFsIG51bWJlciAmbmRhc2g7IHRoZSBtaW5pbXVtIGFtb3VudCBvZiBtb25leSBpbiBFdXJvcyBmb3Igd2hpY2ggVmFsZW50aW5lIGNhbiBidXkgYXQgbGVhc3QgTiByb3Nlcy4gSXQgaXMga25vd24gdGhhdCBmb3IgYWxsIGdpdmVuIHRlc3QgY2FzZXMgdGhlIGNvcnJlY3QgYW5zd2VyIGRvZXMgbm90IGV4Y2VlZCAxMDxzdXA+MTg8XC9zdXA+LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5WYWxlbnRpbmUgd2lsbCBidXkgb25lIGJvdXF1ZXQgYXQgdGhlIGZpcnN0IHBsYWNlIGFuZCB0d28gYXQgdGhlIHNlY29uZC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 P1번