Những năm gần đây, mạng 4G đã được đưa vào khai thác, mọi người có thể dễ dàng truy cập Internet tốc độ cao ở mọi lúc và mọi nơi. Tuy vậy chi phí không phải rẻ lắm, cứ mỗi \(1\) MB tải về người phải trả \(1\) đơn vị thanh toán. Với mục đích khuyến khích sử dụng rộng rãi \(4G\) nhà mạng đưa ra \(2\) gói dịch vụ khuyến mãi trả trước. Với gói thứ nhất cứ mỗi lần dùng có thể tải về \(p\) MB với giá \(q\) đơn vị thanh toán, với gói thứ 2 – tải về \(u\) MB với giá \(v\) đơn vị thanh toán (\(p > q, u > v\)). Người dùng có thể số lượng tùy ý các gói dịch vụ. Mỗi gói dịch vụ chỉ có tác dụng trong một tháng kể từ ngày mua.

Bob có nhu cầu tải về \(n\) MB và muốn tải về với chi phí ít nhất. Có thể một gói dịch vụ nào đó được mua và dùng không hết khả năng cho phép cũng không sao, miễn là tổng chi phí phải ít nhất. Ví dụ, với \(n = 35, p = 10, q = 9, u = 20, v = 17\), Bob sẽ mua một gói dịch vụ thứ nhất, một gói dịch vụ thứ hai, tải về 30MB theo 2 gói dịch vụ đã mua, còn là 5MB – tải về theo chế độ chung. Như vậy tổng chi phí sẽ là 9 + 17+ 5 = 31.

Yêu cầu:

• Cho \(n, p, q, u, v\). Hãy xác định tổng chi phí nhỏ nhất cần thiết để tải về \(n\) MB.

Input:

• Chứa 5 số nguyên dương \(n, p, q, u, v\), mỗi số trên một dòng và có giá trị không vượt quá \(5× 10^5\).

Output:

• Một số nguyên là chi phí nhỏ nhất tìm được.

35 10 9 20 17

31

Nguồn: 2019 CLQĐ-BĐ