시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 274 30 26 20.472%

문제

상근이는 발렌타인 데이를 기념해 여자친구에게 노란 장미 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+XHVjNzQ0IFx1YjExOFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1Y2NhYiBcdWJjODhcdWM5ZjggXHVhZjQzIFx1YzlkMVx1YzVkMFx1YzExYyBcdWFmNDMgXHViMmU0XHViYzFjIDFcdWFjMWMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHVhZjQzIFx1YzlkMVx1YzVkMFx1YzExYyAyXHVhYzFjXHViOTdjIFx1YWQ2Y1x1YjllNFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMzNDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSb3NlcyIsImRlc2NyaXB0aW9uIjoiPHA+VmFsZW50aW5lIGhhcyBkZWNpZGVkIHRvIGNvbmdyYXR1bGF0ZSBhbGwgb2YgaGlzIE4gZ2lybGZyaWVuZHMgYnkgZ2l2aW5nIGVhY2ggb25lIGEgeWVsbG93IHJvc2UuIEluIHRoZSBuZWFyYnkgZmxvd2VyIG1hcmtldCB5ZWxsb3cgcm9zZXMgYXJlIHNvbGQgYnkgZXhhY3RseSB0d28gdmVuZG9ycy4gRWFjaCBvZiB0aGVtIGhhcyBhbiB1bmxpbWl0ZWQgYW1vdW50IG9mIHJvc2VzOyBob3dldmVyLCB0aGV5IHNlbGwgcm9zZXMgb25seSBpbiBib3VxdWV0cyAoc28geW91IGNhbiBvbmx5IGJ1eSBhIGNlcnRhaW4gYW1vdW50IG9mIHJvc2VzIGF0IGEgdGltZSkuIEF0IHRoZSBmaXJzdCB2ZW5kb3IgeW91IGNhbiBidXkgYSBib3VxdWV0IG9mIEEgcm9zZXMgZm9yIEIgRXVyb3M7IGF0IHRoZSBzZWNvbmQgdmVuZG9yICZuZGFzaDsgYSBib3VxdWV0IG9mIEMgcm9zZXMgZm9yIEQgRXVyb3MuIEEsIEIsIEMsIGFuZCBEIGFyZSBhbGwgcG9zaXRpdmUgaW50ZWdlcnMuIElmIFZhbGVudGluZSBjYW4gYnV5IG1vcmUgdGhhbiBOIHJvc2VzIGZvciBhIHNtYWxsZXIgYW1vdW50IG9mIG1vbmV5IHRoYW4gYnV5aW5nIHByZWNpc2VseSBOIHJvc2VzLCBoZSB3aWxsIGJ1eSBtb3JlIHRoYW4gTiByb3NlcyBhbmQgZ2lmdCB0aGUgbGVmdG92ZXIgdG8gYW55IG9mIHRoZSB0d28gbG92ZWx5ICZuYnNwO3NhbGVzZ2lybHMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGNhbGN1bGF0ZXMgdGhlIG1pbmltdW0gYW1vdW50IG9mIG1vbmV5IGluIEV1cm9zIGZvciB3aGljaCBWYWxlbnRpbmUgY2FuIGJ1eSBhdCBsZWFzdCBOIHJvc2VzISZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnRhaW5zIGV4YWN0bHkgb25lIGxpbmUuIFRoZSBmaXJzdCBhbmQgb25seSBsaW5lIGNvbnRhaW5zIGZpdmUgaW50ZWdlcnM6IE4sIEEsIEIsIEMsIGFuZCBEOyBldmVyeSB0d28gY29uc2VjdXRpdmUgbnVtYmVycyBhcmUgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHdoaXRlc3BhY2UuIFRoZSB2YWx1ZSBvZiBOIGRvZXMgbm90IGV4Y2VlZCAxMDxzdXA+MTU8XC9zdXA+LCB0aGUgdmFsdWVzIG9mIEEsIEIsIEMsIGFuZCBEIGRvIG5vdCBleGNlZWQgMTA8c3VwPjU8XC9zdXA+LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgc2hvdWxkIGNvbnRhaW4gb25lIGxpbmUgd2l0aCBvbmUgbmF0dXJhbCBudW1iZXIgJm5kYXNoOyB0aGUgbWluaW11bSBhbW91bnQgb2YgbW9uZXkgaW4gRXVyb3MgZm9yIHdoaWNoIFZhbGVudGluZSBjYW4gYnV5IGF0IGxlYXN0IE4gcm9zZXMuIEl0IGlzIGtub3duIHRoYXQgZm9yIGFsbCBnaXZlbiB0ZXN0IGNhc2VzIHRoZSBjb3JyZWN0IGFuc3dlciBkb2VzIG5vdCBleGNlZWQgMTA8c3VwPjE4PFwvc3VwPi48XC9wPlxyXG4iLCJoaW50IjoiPHA+VmFsZW50aW5lIHdpbGwgYnV5IG9uZSBib3VxdWV0IGF0IHRoZSBmaXJzdCBwbGFjZSBhbmQgdHdvIGF0IHRoZSBzZWNvbmQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Olympiad > Baltic Olympiad in Informatics > BOI 2012 P1번