Security Company

Myungwoo works for a security company and is responsible for patrolling, on foot, several stores near a subway station.

The area can be represented as a single line segment. Myungwoo's office and the stores are placed, from left to right, on points $p_1, p_2, \dots, p_N$ on this segment. The office is at $p_a$, and this point is the starting point $s = p_a$. Myungwoo starts patrolling at $s$ and must visit every store $p_i$ at least once.

The time needed to travel between two adjacent points $p_i$ and $p_{i+1}$ is $t[p_i, p_{i+1}]$. The waiting time $\ell_i$ of point $p_i$ is the time elapsed from leaving the start $s$ until first arriving at $p_i$. The waiting time $\ell_a$ of the start $s = p_a$ itself is $0$. Myungwoo must choose a patrol route that minimizes the sum of the waiting times of all stores.

For example, suppose there are $6$ stores $p_1$ through $p_6$, the start is $s = p_3$, and $t[p_1,p_2] = 7$, $t[p_2,p_3] = 4$, $t[p_3,p_4] = 1$, $t[p_4,p_5] = 2$, $t[p_5,p_6] = 9$. If Myungwoo starts by walking right from $s$, the waiting times $\ell_4$ and $\ell_5$ become $1$ and $3$. With a suitable patrol order the sum of the waiting times can be made $71$, and no method achieves a smaller sum.

Given the number of points $N$ and the travel times $t[p_i, p_{i+1}]$ ($i = 1, \dots, N-1$) between adjacent points, write a program that finds the minimum possible sum of the waiting times.

The first line contains the number of test cases $T$. Each test case is structured as follows.

• The first line contains the number of stores $N$ ($1 \le N \le 100$).
• The second line contains the position of the starting point $a$ ($1 \le a \le N$). The $a$-th point $p_a = s$ is the starting point.
• Each of the next $N-1$ lines, the $i$-th of them, contains $t[p_i, p_{i+1}]$ ($1 \le t[p_i, p_{i+1}] \le 15\,000\,000$).

For each test case, print on its own line the minimum sum of the waiting times over all ways of patrolling every store.