좁은 미술관

길쭉한 미술관에 방이 $2N$개 있다. 미술관은 세로로 $N$줄, 가로로 2칸인 격자 모양이고, 위아래로 붙은 방과 양옆으로 붙은 방은 서로 통한다. 오늘 근무하는 큐레이터는 운영비를 줄이려고 방 $k$개를 닫으라는 통보를 받았다.

관람객은 한쪽 끝 줄의 두 방 중 적어도 한 곳으로 들어와서 반대쪽 끝 줄의 두 방 중 한 곳으로 나갈 수 있어야 한다. 그러려면 큐레이터는 같은 줄에 있는 두 방을 모두 닫아서는 안 되고, 대각선으로 맞닿은 두 방을 함께 닫아서도 안 된다. 같은 세로 열에서 위아래로 붙은 두 방을 닫는 것은 괜찮다.

각 방을 공개했을 때 얼마나 큰 가치가 생기는지는 큐레이터가 이미 알고 있다. 위 조건을 지키면서 방을 정확히 $k$개 닫을 때, 열려 있는 방의 가치 합을 최대로 만들어라.

입력은 미술관 여러 개로 이루어진다. 각 미술관의 첫 줄에는 두 정수 $N$과 $k$ ($3 \le N \le 200$, $0 \le k \le N$)가 주어진다. $N$은 미술관의 세로 길이이고, $k$는 닫아야 하는 방의 수이다. 이어지는 $N$개의 줄에는 줄마다 두 정수가 주어지며, 그 줄의 왼쪽 방과 오른쪽 방의 가치를 뜻한다. 각 방의 가치 $v$는 0 이상 100 이하이다.

마지막 미술관의 정보 뒤에는 0 0이 한 줄 주어지고 입력이 끝난다.

미술관마다 관람객에게 공개할 수 있는 가치의 최대 합을 한 줄에 하나씩, 입력에 나온 순서대로 출력한다.