Tomya is a girl. She loves Chef Ciel very much.

Since Tomya has completed collecting the stamps in Ciel's restaurant, she now challenges the bonus game in her restaurant. There are colored balls in a box. The number of colors is N, and the number of balls color i in the box is S_i for i = 1, 2, ..., N initially. At first, Tomya has M coins. And Tomya's aim in this game is to get many coins at the end of the game. This game will run as follows.