Let's denote the lower left corner of the screen (the snake's initial position) with the coordinate ~(0, 0)~ and the upper right corner with the coordinate ~(R-1, S-1)~. Let ~h~ be the largest row number that contains at least one apple. It is evident that the number of presses of button B is equal to ~h~.

We are left with the problem of the number of presses of button A. Let's assume that the snake is located at row ~r~ and column ~s~. Depending on the parity of number ~r~, the snake is facing to the left (odd ~r~) or to the right (even ~r~). Let's analyze the necessary steps the snake must do in the given situation.

If the snake is facing to the left and row ~r~ contains an apple that is located at a column number smaller than ~s~, it is necessary to keep pressing the A button until we get to at least that apple. Additionally, if the row above (numbered ~r+1~) contains an apple that is located at a column number smaller than ~s~, it is necessary to keep pressing the A button until we get to at least that column (otherwise, we won't be able to eat that apple). Only then can we press button B and move upwards.

Analogously, if the snake is facing to the right, it is necessary to keep pressing the A button to position the snake to at least the maximum column number that contains an apple in rows ~r~ or ~r+1~.

Is it possible to reduce the number of necessary steps in one of the following rows by exceeding the number of necessary steps in the current row? It is visible that we increase (or don't change) the number of necessary steps in the row above when we exceed the number of necessary steps in the current row. Inductively, it is clear that by using necessary movements in each row we will obtain the path of optimal length.