What can be better than a whopper? Only a double whopper! And what about a $$$k$$$-whopper? Bob wants to eat like a pig, but Alice wants to stop him!

A reform was made in "Burger King", and now there are $$$n$$$ cash desks there, numbered from $$$0$$$ to $$$n - 1$$$. For each cash desk, two numbers are given: $$$a_i$$$ and $$$k_i$$$ — the change in the number of patties in the whopper after visiting this cash desk, and its importance, respectively. The value $$$a_i$$$ can be negative, then the number of patties decreases.

All visitors start at cash desk $$$n - 1$$$ and then move between cash desks until they reach cash desk $$$0$$$. While at cash desk with number $$$i$$$ ($$$0 \lt i \lt n$$$), one can move either to cash desk $$$i - 1$$$, or choose a number $$$b$$$ ($$$1 \lt b \le k_i$$$) and move to cash desk $$$\lfloor i / b \rfloor$$$.

Before visiting cash desk $$$n-1$$$, Bob's whopper contains $$$10^{100}$$$ patties (did you think we were bluffing in the first paragraph?). When visiting cash desk with number $$$i$$$, exactly $$$a_i$$$ patties are added to the whopper, and it is impossible not to take them. Alice and Bob make moves alternately, and Alice moves first. Alice wants to minimize the final number of patties, while Bob wants to maximize it. On their move, Alice or Bob chooses the next cash desk to move to.

Determine how many patties will be in the whopper if both players play optimally.

The tests for this problem consist of seven groups. Points for each group are given only if all tests of this group and all tests of some previous groups are passed. Please note that passing the sample tests is not required for some groups. The final score for each group is equal to the maximum score obtained for this group over all submissions.