로봇의 이동

무한히 넓은 격자판 위에 로봇이 한 대 놓여 있다. 격자판은 1×1 크기의 칸으로 나뉘어 있고, 각 칸은 좌표 $(x, y)$로 나타낸다. 로봇은 칸 하나를 차지하며, 처음 위치는 $(0, 0)$이다.

로봇에는 수행할 연산이 미리 프로그램되어 있다. 연산은 U, D, L, R 네 가지이고, U는 위로, D는 아래로, L은 왼쪽으로, R은 오른쪽으로 한 칸 이동하는 연산이다. 전원이 켜지면 로봇은 프로그램된 연산을 앞에서부터 차례로 하나씩 수행하고, 마지막 연산까지 끝내면 이동을 멈추고 스스로 전원을 끈다.

로봇은 $(0, 0)$ 칸에 도착할 때마다 박수를 친다. 프로그램된 연산을 바꿔서 $(0, 0)$을 방문하는 횟수를 최대로 만들려고 한다. 연산은 최대 $M$번 바꿀 수 있다. 연산을 한 번 바꾸는 것은 연산 문자열에서 문자 하나를 골라 다른 문자로 바꾸는 것을 뜻한다. 문자를 새로 넣거나 지우는 것은 안 된다.

출발 위치인 $(0, 0)$은 방문 횟수에 넣지 않는다. 연산을 하나 수행한 직후에 로봇이 $(0, 0)$에 서 있는 경우만 센다.

연산 문자열 $S$와 정수 $M$이 주어졌을 때, $(0, 0)$을 방문하는 횟수의 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 로봇에 프로그램되어 있는 연산 $S$가 주어진다. $S$는 U, D, L, R로만 이루어져 있다. 둘째 줄에 정수 $M$이 주어진다.

$S$의 길이를 $L$이라고 할 때 $2 \le L \le 300$, $0 \le M \le L$이다.

연산을 최대 $M$번 바꿔서 얻을 수 있는 $(0, 0)$ 방문 횟수의 최댓값을 첫째 줄에 출력한다.

$S$가 UULRRLLL이고 $M$이 1인 경우, 첫 번째 U를 D로 바꾸면 $(0, 0)$을 세 번 방문한다. 두 번째 U를 D로 바꿔도 방문 횟수는 세 번이다.