문제
In order to save money for a new stall in her barn, Bessie the cow has started performing in the local circus, demonstrating her remarkable sense of balance as she carefully walks back and forth on an elevated balance beam!
The amount of money Bessie earns in her performance is related to where she manages to ultimately jump off the beam. The beam has positions labeled
If Bessie is at a given position
1. Flip a coin. If she sees tails, she goes to position
2. Jump off the beam and receive payment of
Bessie realizes that she may not be able to guarantee any particular payment outcome, since her movement is governed by random coin flips. However, based on the location where she starts, she wants to determine what her expected payment will be if she makes an optimal sequence of decisions ("optimal" meaning that the decisions lead to the highest possible expected payment). For example, if her strategy earns her payment of
Problem credits: Franklyn Wang and Spencer Compton
입력
The first line of input contains
출력
Output
예제1
2
1
3
150000
300000