배고픈 땅돼지 아르디

아르디는 지치고 배고픈 상태로 애완동물 가게에 도착했다. 옆 선반에는 맛있어 보이는 바삭한 개미가 가득한 개미집이 있었다. 이 개미집은 2차원이라서 모든 터널과 개미가 한눈에 들어왔다. 아르디는 가게가 문을 닫은 뒤 허기를 채울 방법을 곧바로 궁리하기 시작한다. 그녀의 혀 길이는 30cm로, 땅돼지의 평균적인 길이다. 그녀는 터널 구간의 길이를 어림잡을 수 있고, 구간 안의 개미 수를 셀 수 있다. 목표는 제한된 횟수의 긴 혀 탐침으로 가능한 한 빨리 들어갔다 나와서 가장 많은 개미를 잡는 것이다. 땅돼지는 계산에 강하지 않으므로, 아르디는 분석을 도와 주기를 바란다.

식사를 준비하면서 아르디는 혀가 터널로 들어갈 수 있는 최장 경로를 여러 개 (전부일 필요는 없다) 살펴보기를 바란다. 이 계산을 미리 해 두면, 제한된 식사 시간에 탐침할 최적의 경로를 고를 수 있다.

개미집의 입구는 하나이며 'a'로 표시한다. 이 지점에서 터널은 최대 두 갈래로 나뉘어 왼쪽이나 오른쪽으로 이어진다. 각 갈래는 그 아래의 교차점에서 같은 방식으로 다시 나뉠 수 있다. 기록된 최장 경로마다 아르디는 각 터널 구간의 길이와, 각 교차점에서 택할 방향을 기록한다. 방향은 혀가 탐침하는 방향을 기준으로 한 L(왼쪽)과 R(오른쪽)로 표시한다. 혀가 닿는 30cm 범위를 완전히 벗어난 구간은 기록하지 않는다. 탐침은 막다른 곳에서 끝나거나, 혀가 닿는 최대 거리에서 구간 중간에 끝난다. 터널이 좁아서 같은 탐침 안에서 혀를 되돌려 다른 갈래로 내려갈 수는 없다. 아르디는 경로의 각 구간에서 닿는 개미 수를 기록했다. 목표는 그녀의 혀가 닿을 수 있는 개미의 최대 총합을 계산하는 것이다.

첫 줄에는 두 정수가 주어진다. 하나는 아르디가 기록한 경로의 수이고, 다른 하나는 그녀가 수행할 수 있는 탐침의 횟수이다. 이어지는 각 줄은 순서와 상관없이 주어지는 최장 경로 하나를 나타낸다. 경로 줄은 구간의 수로 시작하고, 그 뒤에 구간들이 순서대로 나온다. 각 구간은 네 가지 요소로 이루어진다. R은 오른쪽 회전, L은 왼쪽 회전을 뜻한다. 다음은 구간의 추정 전체 길이(양의 정수이며, 끝이 혀가 닿지 않는 범위에 있어도 전체 길이를 준다)이다. 그다음은 구간에서 닿는 개미 수(범위 밖에 더 있을 수 있다)이고, 마지막은 구간 끝에 있는 노드를 가리키는 소문자이다. 노드는 교차점일 수도 있고 막다른 곳일 수도 있다. 노드는 처음 조사되는 순서대로 a부터 이름이 붙는다.

아르디는 20회를 넘는 탐침을 요청하지 않는다. 같은 탐침 안에서 노드나 구간이 반복되지 않는다. 두 후보 경로가 더 아래에서 합쳐지지 않는다. 어떤 터널 구간에도 개미는 100마리를 넘지 않는다.

주어진 탐침 횟수로, 제시된 최장 경로들의 조합을 통해 아르디가 잡을 수 있는 개미의 최대 수를 한 정수로 출력한다.

원래 문제의 그림은 샘플 구성을 보여 준다. 경로 2(abdef)는 4+7+3+1=15마리에 닿으므로, 탐침이 한 번이면 최댓값은 15이다. 탐침이 두 번이면 경로 2(abdef)와 경로 6(aik)은 완전히 겹치지 않는다. 경로 3(abdeg)과 경로 4(abdh)는 각각 경로 2보다 많은 개미를 가지고 있지만, 그 대부분은 경로 6의 탐침에서 이미 잡힌다. 따라서 경로 2와 경로 6의 개미 27마리가 최적이다.