## BRTREE - Bread Tree

 English Vietnamese

Breadtree is a kind of tree that produces bread. At its first year, a breadtree is only a node with a bread of weight 0 on this node which is also called zeronode. Every year after that, the weight of bread on each node of the tree will increase by 1, and another branch with a zeronode will grow at the end of each node. However, there is a limit of branches on each node. That is, when the number of branches of a node reaches the limit, there won't be any more branches, but the weight of its bread will still increase. What's more, a breadtree remains unchanged when the total weight of bread is larger than 1234567890.

### Input

There are two integers N and K on each line. N is a positive integer fit in signed 32-bit integer. K is a non-negative integer fit in signed 32-bit integer. An N equals to 0 signals the end of input, which should not be processed.

### Output

Output the total weight of bread on a breadtree with branches limit K in the N-th year in a line for each case.

### Example

```Input:
10000 0
101 1
10 2
1221 128
0 0

Output:
9999
5050
221
2147483647```

hide comments
 noedelorme: 2021-07-20 02:11:51 [Fixed] I have really fast solution which seems to work on every test I can imagine. But I still have a WA. Is there any way to access the input file (or maybe only the test case that doesn't work)? Last edit: 2021-07-20 19:49:57 noedelorme: 2021-07-19 22:52:36 @legsleg True, my bad :-) legsleg: 2021-07-19 10:07:48 The worst-case input regarding running-time is actually (most probably) something else. Last edit: 2021-07-19 10:11:07 jacomo: 2021-07-17 13:10:25 @noedelorme: It's done in under 0.1s Last edit: 2021-07-17 13:10:42 noedelorme: 2021-07-17 08:39:22 You can try with the worst case, which is the following (because 2147483647 is the maximal positive signed 32-bit integer) : 2147483647 2147483647 0 0 jacomo: 2021-07-13 09:16:24 Getting always a TLE , but don't know why. Is it possible to get an example for the testcase inputs?

 Added by: Race with time Date: 2009-01-24 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ERL JS-RHINO NODEJS PERL6 VB.NET Resource: ZOJ Monthly, January 2009 - A