Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

BRTREE - Bread Tree

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274485/problem/A
{assign var="code" value="BRTREE"} {if $par==""} {assign var=par value=$locale} {/if}
{if $par=="en"} {literal}

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

{/literal}{elseif ($par=="vn" || $par=="")}{literal}

Cây bánh mì là một loài cây chuyên sản xuất bánh mì. Ở năm đầu tiên, một cây bánh mì chỉ có một nút với một chiếc bánh mì có trọng lượng 0 ở nút đó, gọi là nút 0. Cứ mỗi năm sau đó, trọng lượng của bánh mì trên mỗi nút của cây sẽ tăng thêm 1, và một cành với một nút 0 sẽ mọc thêm vào cuối mỗi nút. Tuy nhiên, có một giới hạn về số cành trên mỗi nút. Tức là, khi số lượng cành của một nút đạt đến giới hạn thì sẽ không có thêm cành nào mọc thêm ở nút đó nữa, nhưng trọng lượng của chiếc bánh mì của nó thì vẫn tăng lên. Thêm vào đó, một cây bánh mì sẽ không thay đổi nữa khi mà tổng trọng lượng của những chiếc bánh mì trên nó lớn hơn 1234567890.

Input

Có nhiều bộ test, mỗi bộ test gồm 2 số nguyên N và K trên 1 dòng. N và K đều là các số nguyên dương 32-bit. N bằng 0 đánh dấu kết thúc input và không cần xử lí.

Output

Với mỗi bộ test, viết ra tổng trọng lượng của những chiếc bánh mì trên cây vào năm thứ N, khi biết giới hạn số cành là K.

Example

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


Output:
9999
5050
221
2147483647

{/literal} {/if}

Được gửi lên bởi:Race with time
Ngày:2009-01-24
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET
Nguồn bài:ZOJ Monthly, January 2009 - A

hide comments
2015-07-02 09:30:41 there's no salvation for me...
duyệt trâu AC mà :3
2012-10-25 14:28:57 Ðẹp trai có gì sai
min(n,43) thôi :D
2011-11-13 11:46:41 Noyethug
QHD......độ phức tạp khoảng min(n,50k)*sotest

Last edit: 2011-11-13 12:01:25
2010-02-09 07:26:23 Tue Le
"N và K đều là các số nguyên dương 32-bit"
Test VD có K=0 kìa anh Quang :-??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.