-= Puzzle 7: Ross's Pet Snake =-

It's your seventh day at BitFlop Laboratories, and you can't believe you survived a full week of work.

Well, not yet actually, you still have to work today to finish the week.

You decide to help your colleague Ross.

Ross is the company's self-proclaimed snake and sushi expert, and he proudly introduces you to his beloved pet snake.

Unfortunately, the snake isn't that smart.

In fact, it refuses to make a single decision on its own and will only move exactly as Ross instructs.

The snake lives on a grid and can move up, down, left or right. On the grid, there is also sushi that the snake can eat.

Ross hands you today's instructions (your puzzle input), which consist of two parts:

• A sequence of movement instructions.
• A list of sushi locations, in the order they will appear.

The movement instructions use the following characters:

• >: Move right.
• <: Move left.
• ^: Move up.
• v: Move down.

Only one piece of sushi is present on the board at any time, and as soon as the snake eats it, the next piece of sushi appears at the next coordinates in the list.

For example:

>>>^>>v<^<^>>>>v<^^>vv>^<^^^^^<^<vv>^^^>

3,0
5,1
5,0
3,2
7,1
6,1
7,3
7,1
7,6
5,8
5,7
6,6
7,9

The first line contains the movement instructions.

The coordinates below it (after the blank line) are the sushi locations, in the order they appear.

For this example we use a 10 by 10 grid, while your actual puzzle input uses a 30 by 30 grid.

The snake always starts at (x: 0, y: 0) (bottom-left corner), and occording to the list, the first piece of sushi appears at (x: 3, y: 0).

The following diagrams show the beginning of the example, where (x: 0, y: 0) is the bottom-left corner. S is the snake, and @ is the current piece of sushi.

0. Initial state:
..........
..........
..........
..........
..........
..........
..........
..........
..........
S..@......

1. Move >
..........
..........
..........
..........
..........
..........
..........
..........
..........
.S.@......

2. Move >
..........
..........
..........
..........
..........
..........
..........
..........
..........
..S@......

3. Move >
..........
..........
..........
..........
..........
..........
..........
..........
.....@....
...S......

After the third move, the snake eats the first piece of sushi, so the second piece of sushi in the list appears at (x: 5, y: 1)

4. Move ^
..........
..........
..........
..........
..........
..........
..........
..........
...S.@....
..........

5. Move >
..........
..........
..........
..........
..........
..........
..........
..........
....S@....
..........

6. Move >
..........
..........
..........
..........
..........
..........
..........
..........
.....S....
.....@....

After the sixth move, the snake eats the second piece of sushi, causing the third piece of sushi to appear at (x: 5, y: 0).

For now, you only need to consider the first half of the movement instructions.

In the example, after the first 20 instructions (half of the total 40), the snake has eaten 7 pieces of sushi and finishes at (x: 7, y: 3).

The main grid is 30 by 30 instead of 10 by 10 in the example, and the snake will follow the first 2500 of the 5000 movement instructions.

Don't worry, the input guarantees the snake never leaves the grid.

How many pieces of sushi does the snake eat after following the first 2500 of the 5000 movement instructions?