ZOJ Problem Set - 3385
Saigyouji Yuyuko and Konpaku Youmu are going to hold a hanami party (a Japanese traditional custom of enjoying the beauty of cherry blossoms). They decide to invite all their friends to come to the yard enjoying the feast under the flowering trees, and sometimes the party will go on until late at night.
To prepare for the grand party, Youmu need to make as much food as possible. But soon she noticed that the "hungry ghost" Yuyuko will eat some food she made every day. If there is no enough food, the hungry Yuyuko will become angry.
They have N days to prepare for the party. On the first day of their preparation, Youmu has an initial cooking level L, which means she can make L units of food in one day. Everyday, Youmu can choose to do only one of the actions below:
Anyway, Youmu don't want to enrage Yuyuko, so she turned to you for help. You should maximize the amount of food Youmu can present on the party, without making Yuyuko angry.
There are multiple test cases (no more than 20).
The first line contains two integers N and L (1 <= N <= 100000, 0 <= L <= 10^9). The second line contains N integers ai (0 <= ai <= 10^9), which means on the ith day of their preparation, Yuyuko will eat ai units of food that Youmu made.
If Yuyuko won't get angry during the preparation, output the maximal amount of food Youmu can present on the party. Otherwise, output a line of "Myon".
5 2 1 1 1 4 2
Author: JIANG, Kai
Source: ACM × Touhou
Contest: ZOJ Monthly, August 2010