Space Invaders

Space Invaders

Peterwrote hisversion of thepopular game"Space Invaders".The gameis as follows.Onthe groundattackships ofSpace Invaders.Theylined upin rowsat the topof the screen.The player controls alaser gun, which is locatedat the bottom ofthe screenin one of thecolumns.Forone actiona player canmove thegunleft or right, ormake a shotstraight up.If a playermakesa shot, itdestroys thealien shipcomingin thatcolumn,in which thegun.


Unlike the originalgame,Petyaembodiment ofalien shipsarein place andcan not shoot, so theplayer can notlose.Help thePetedestroy allalien shipsin a minimumnumber of operations.


The firstline containsthe numbern and p - number of columns andcolumn number, whichis initiallya gun (1n100, 1pn). The second linecontainsn numbersa1, a2, ..., an, where ai - the number ofaliensin the ith column (1ai100).


In theoutput fileoutputa single number -the minimum number ofoperationsrequiredtodestroy all thealiens.

Time limit 1 second
Memory limit 64 MiB
Input example #1
5 4
5 3 4 1 2
Output example #1
Author Georgiy Korneev, Pavel Mavrin