Problem G
Magic Fish

Mister Blue fishing

Wanda can’t swim, but she knows a series of magic tricks that allows her to jump over water from one place to another. Each magic trick is characterized by a number $x$. If Wanda knows magic trick $x$ this means that she can jump a distance of $x$ to the East or to the West at any time.

In some special locations there are wizards that can teach Wanda new tricks for a certain cost.

In another location, $B$ feet East from Wanda’s starting location, Mister Blue, the fishing cat, is fishing. If Wanda ends a jump just in front of Mister Blue then he fishes her out, so she wants to avoid that.

You are to decide if it is possible for Wanda to reach home while avoiding Mister Blue, and if so, what is the cheapest way to do so.

For example, if Wanda’s house is $4$ feet to her East, Mister Blue is $2$ feet, and currently Wanda only knows trick $2$, it’s impossible for her to avoid Mister Blue. If there is a wizard at location $-8$ who is willing to sell trick $3$ for $42$ dollars, then Wanda can reach home by visiting the following locations in order: $0$, $-2$, $-4$, $-6$, $-8$ (at this point she purchases the new magic trick), $-5$, $-2$, $1$, $4$.

Input

The first line of the input contains $4$ integers: $H$, $B$, $M$, and $N$ containing the location of Wanda’s house, Blue’s location, the number of tricks Wanda already knows, and the number of wizards. $-10^{18} \le H, B \le 10^{18}$, $B \neq 0$, $B \neq H$, $1 \le M \le 1\, 000$, and $0 \le N \le 1\, 000$.

The next line contains $M$ space-separated integers, indicating the tricks Wanda already knows. All tricks are between $1$ and $10^9$.

Each of the following $N$ lines contains three integers: $l$, $t$, and $c$ indicating the location (with respect to Wanda’s original location) of a wizard, the trick they can teach, and the cost they charge. $-10^{18} \le l \le 10^{18}$, $1 \le t \le 10^9$, $0 \le c \le 1\, 000\, 000$.

Output

Output a single integer containing the cheapest way for Wanda to reach home while avoiding Mister Blue. If there are no ways for Wanda to get home output $-1$.

4 2 1 0
2

-1

4 2 1 1
2
-8 3 42

42

2 100000 1 1
6
12 4 1000

1000