Welcome to Galilei Town, a high and new technology industrial development zone surrounding the Dishui lake. N villages numbered from 0 to N −1 are located along the lake and a loop-line bus is the only transportation in this town. The bus is a one-way line passing the villages 0,1,2,··· ,N −1 successively, going back to the 0-th village and continuing the above route. 

We may measure the landscape of the i-th villages by an integer w_i and . Once a traveller takes the bus from the u-th village to the v-th village, he would evaluate the experience by two coefficients a = w_v and b the sum of w(s) for all passing villages (including the last stop and excluding the first one).

Now, as the tour guide, you need to design a travel brochure for guests who came from far away. Your task is to choose a village i₀ as the starting village of the travel and at least two more villages i₁,i₂,··· ,i_k. Guests would start their travel from the i₀-th village and visit the planned k villages in sequence by loop-line bus. Finally they will go back to the i₀-th village from the i_k-th one and finish their travel. If we let i_k+1 = i₀, the whole travel would be evaluated by the score  . You need to know the maximum possible score.