Background

@Ge Jun Original.

As an OIer, Fumino Furuhashi works hard on Luogu every day. However, her parents think she is addicted to the Internet, so they send her to Yang Jiaoshou’s Internet Addiction Treatment Center.

One year later, thanks to unremitting effort, Fumino Furuhashi finally escapes. She immediately reports Yang Jiaoshou’s actions to the police. After learning the situation, the police ask her to lead the way to the center to arrest Yang Jiaoshou.

Problem Description

Ah~~~~！

As soon as they arrive at the Internet Addiction Treatment Center, they hear screams coming from inside. Fumino Furuhashi has stayed in the center for a year and is very familiar with it, so she immediately knows that Uncle Yang is “counting cash” again in Treatment Room No. $13$. At the same time, she knows the center has $n$ rooms, and any two rooms are connected by corridors. There is a door between each corridor and each room. The doors are locked from the outside, and will automatically lock again after being opened (that is, each time you go from room $i$ into any corridor connected to it, you need to spend $c_i$ stamina to unlock it, while entering a room from a corridor costs no stamina).

To prevent “allies” from escaping, Uncle Yang installs cameras in every room, and assigns $n$ underlings in the monitoring center to watch the feeds.

In particular, Room $\bf1$ is the monitoring center. Underling $\bf1$ is responsible for preventing anyone (except Uncle Yang) from entering the monitoring center (otherwise he reports to Uncle Yang immediately). The other underlings from No. $2$ to No. $n$ each monitor rooms whose numbers are integer multiples of their own number (for example, when $n=10$, underling No. $2$ monitors Rooms No. $2$, $4$, $6$, $8$, $10$). Treatment Room No. $13$ is also monitored by this rule. If any one of them sees the same person twice, they will report to Uncle Yang (but the underlings do not share information with each other). Fortunately, these underlings are strong but simple-minded, and can only remember what happened in the previous second.

To ensure the arrest goes smoothly, Fumino Furuhashi and the police must not be discovered. They are currently in Room $x$, and Treatment Room No. $13$ is in Room $y$. It is known that passing through each corridor takes $1$ second, and unlocking doors and passing through rooms takes no time (but will be seen by the underlings in the monitoring center). Fumino Furuhashi and the police want to know the minimum stamina needed to enter Treatment Room No. $13$ without being discovered.

Input Format

This problem has multiple queries.

The first line contains an integer $T$, meaning there are $T$ queries. The second line contains an integer $n$, meaning there are $n$ rooms and underlings (note that in this problem, $n$ is read only once, and this $n$ is the same for every query).

For each query, the first line contains two integers: $x,y$, where $x$ is the room number where Fumino Furuhashi and the police are, and $y$ is the room number of Treatment Room No. $13$. The next line contains $n$ integers, representing $c_i$.

Output Format

Output $T$ lines in total. For each query, output one line with one integer, meaning the minimum stamina needed to enter Treatment Room No. $13$ without being discovered. If it is impossible to reach, output $-1$.

1
5
2 4
1 2 3 4 5

5

Hint

Sample Explanation

One feasible plan is: $2\to3\to4$.

Constraints

For $30\%$ of the testdata, $n\leq1500$, $T\leq15$.

For $50\%$ of the testdata, $n\leq2500$, $T\leq30$.

For $70\%$ of the testdata, $n\leq4500$, $T\leq50$.

For $100\%$ of the testdata, $n\leq4500$, $T\leq200$, $2\leq x,y\leq n$, $c_i\leq9900$.

Note

The input size may be large. Fast input and O2 optimization are recommended.

Translated by ChatGPT 5