In the capital city of Berland, Bertown, demonstrations are against the recent election of the King of Berland. Berland opposition, led by Mr. Ovalny, believes that the elections were not fair enough and wants to organize a demonstration at one of the squares. Bertown has n squares, numbered from 1 to n , they are numbered in the order of increasing distance between them and the city center. That is, square number 1 is central, and square number n is the farthest from the center. Naturally, the opposition wants to hold a meeting as close to the city center as possible (that is, they want an square with the minimum number). There are exactly k ( k < n ) days left before the demonstration. Now all squares are free. But the Bertown city administration never sleeps, and the approval of an application for the demonstration threatens to become a very complex process. The process of approval lasts several days, but every day the following procedure takes place: The opposition shall apply to hold a demonstration at a free square (the one which isn't used by the administration). The administration tries to move the demonstration to the worst free square left. To do this, the administration organizes some long-term activities on the square, which is specified in the application of opposition. In other words, the administration starts using the square and it is no longer free. Then the administration proposes to move the opposition demonstration to the worst free square. If the opposition has applied for the worst free square then request is accepted and administration doesn't spend money . If the administration does not have enough money to organize an event on the square in question, the opposition's application is accepted. If administration doesn't have enough money to organize activity, then rest of administration's money spends and application is accepted If the application is not accepted, then the opposition can agree to the administration's proposal (that is