Chicken Coupons

Interview

Time limit2sMemory limit128 MB

Summary
Given n chicken coupons and a stamp-to-coupon exchange rate k, compute the maximum chickens obtainable by repeatedly redeeming stamps for new coupons.
Level

Easy2 of 10

Topics
Math, Simulation, Greedy
Solved
No attempts yet

Problem

Kangmin has n coupons, each of which can be used to order one chicken. Whenever he orders one chicken with a coupon, the shop gives him one stamp. Every k stamps can be exchanged for one new coupon.

Determine the maximum number of chickens Kangmin can eat using the coupons he has now and any coupons he receives by exchanging stamps. A coupon is required to order each chicken.

Input

The input consists of multiple lines. Each line contains two natural numbers n and k separated by a space. Input continues until the end of file.

Output

For each input line, print the maximum number of chickens Kangmin can eat on its own line.

Constraints

  • 1 < k <= n <= 1,000,000,000

Examples1

  1. Example 1

    Input
    4 3
10 3
100 5
    Expected output
    5
14
124