Robot Movement

A robot stands on an infinitely large grid board. The board is divided into cells of size 1×1, and every cell is named by a coordinate $(x, y)$. The robot occupies one cell, and it starts at $(0, 0)$.

The robot comes with a program, a string of operations written with the letters U, D, L, and R. U moves the robot one cell up, D one cell down, L one cell left, and R one cell right. When the power goes on, the robot performs the programmed operations one at a time from the front. After the last operation it stops moving and turns itself off.

The robot claps every time it arrives at cell $(0, 0)$. You want to rewrite the program so that the number of visits to $(0, 0)$ is as large as possible. You may change at most $M$ operations. One change means picking a single character of the program and replacing it with a different character. Inserting a character or deleting one is not allowed.

The starting position $(0, 0)$ is not counted as a visit. Only a moment right after an operation, with the robot standing on $(0, 0)$, counts.

Given the operation string $S$ and the integer $M$, write a program that finds the maximum number of visits to $(0, 0)$.

The first line contains the program $S$ of the robot. $S$ consists only of the letters U, D, L, and R. The second line contains the integer $M$.

Let $L$ be the length of $S$. Then $2 \le L \le 300$ and $0 \le M \le L$.

Print on the first line the maximum number of visits to $(0, 0)$ that at most $M$ changes can produce.

When $S$ is UULRRLLL and $M$ is 1, changing the first U into D gives three visits to $(0, 0)$. Changing the second U into D also gives three visits.