Mô tả
Năm nay, nhà máy may mặc Bình Dương chuẩn bị đón Tết rộn ràng. Ban giám đốc giao cho chị Hạnh — kế toán trưởng — chuẩn bị phong bì lì xì cho N công nhân. Chị định dùng đúng N phong bì, mỗi phong bì chứa một số tờ tiền mới cứng, mỗi tờ đều có mệnh giá K nghìn đồng.
Chị Hạnh muốn mỗi công nhân nhận được một số tiền dương (ít nhất 1 nghìn đồng), nhưng lại không muốn tốn quá nhiều tiền. Vì các tờ tiền chỉ có mệnh giá K nên số tiền mỗi người nhận sẽ là a_i × K (nghìn đồng), trong đó a_i ≥ 1 là số tờ trong phong bì thứ i.
Để tối ưu chi phí, chị Hạnh cần tìm cách phân bổ sao cho tổng số tờ tiền là nhỏ nhất có thể, đồng thời mỗi phong bì vẫn phải có ít nhất một tờ. Hãy giúp chị Hạnh tính xem cần dùng ít nhất bao nhiêu tờ tiền mệnh giá K để chia đủ cho N công nhân.
Đầu vào
Hai số nguyên trên một dòng, cách nhau bởi dấu cách:
N(1 ≤ N ≤ 10⁶): số lượng công nhân (số phong bì).K(1 ≤ K ≤ 10⁶): mệnh giá mỗi tờ tiền, tính bằng nghìn đồng.
Đầu ra
Một số nguyên duy nhất: tổng số tờ tiền mệnh giá K ít nhất cần dùng, sao cho mỗi phong bì có ít nhất 1 tờ và tổng số tờ là nhỏ nhất.
Ràng buộc
- 1 ≤ N ≤ 10⁶
- 1 ≤ K ≤ 10⁶
- Kết quả đảm bảo nhỏ hơn 2³¹ − 1.
Ví dụ
Ví dụ 1:
Input:
5 2
Output:
5
Giải thích: Có 5 công nhân, mỗi người cần ít nhất 1 tờ mệnh giá 2 nghìn đồng. Để tổng số tờ nhỏ nhất, ta cho mỗi người đúng 1 tờ. Tổng số tờ = 5 × 1 = 5. Mỗi người nhận 2 nghìn đồng, tổng tiền đã phát = 10 nghìn đồng.
Ví dụ 2:
Input:
3 10
Output:
3
Giải thích: 3 công nhân, mệnh giá 10 nghìn đồng. Mỗi người nhận đúng 1 tờ (10 nghìn). Tổng số tờ = 3.