G. Grouping Problem
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

In the NTU field, there are $$$N$$$ people standing on a land shaped like a number line, waiting to participate in the unique NTU game. Each person can be considered to be standing at coordinate $$$x_i$$$ on the number line.

As the game master of the event, you need to group these people. For each group, let $$$l$$$ be the minimum coordinate, and $$$r$$$ be the maximum coordinate among the people in the group. Then, you have to pay $$$a + b\times(r - l)$$$ dollars to organize a game for that group.

You quickly realize how to minimize the cost of grouping everyone efficiently. However, you soon discover that the cost is still very high. To address this, you wish to dismiss some people to reduce the overall cost of the game.

After conducting some investigations, you find out that asking the $$$i$$$-th person to leave requires spending $$$c_i$$$ dollars. Moreover, there are $$$M$$$ hidden friend relations among these people. Each friend relation is represented as a triple $$$(u_i, v_i, w_i)$$$, which means there is a friendship between $$$u_i$$$ and $$$v_i$$$. If exactly one person among $$$u$$$ and $$$v$$$ is asked to leave, you will need to spend an additional $$$w_i$$$ dollars to compensate for their friendship!

Despite the complexity of these relationships, you still aim to minimize the total cost of the game. Please write a program that takes the given input and outputs the minimum possible cost.

Input

The input begins with four integers $$$N$$$, $$$M$$$, $$$a$$$, and $$$b$$$, denoting the number of people, the number of friend relations, and the parameters $$$a$$$, $$$b$$$, respectively.

The second line contains $$$N$$$ integers $$$x_1, x_2, \ldots, x_N$$$, representing that the coordinate of the $$$i$$$-th person is $$$x_i$$$.

The third line contains $$$N$$$ integers $$$c_1, c_2, \ldots, c_N$$$, representing that the cost for asking the $$$i$$$-th person to leave.

Following that, $$$M$$$ lines are provided, each containing three integers $$$u_i$$$, $$$v_i$$$, and $$$w_i$$$, representing that the $$$i$$$-th friend relation connecting person $$$u_i$$$ and person $$$v_i$$$ with cost $$$w_i$$$.

  • $$$1 \leq N \leq 200$$$
  • $$$0 \leq M \leq \min(200, \frac{N\times(N-1)}{2})$$$
  • $$$1 \leq a, b, c_i, w_i \leq 10^9$$$
  • $$$1 \leq x_1 \lt x_2 \lt \cdots \lt x_N \leq 10^6$$$
  • $$$1 \leq u_i, v_i \leq N$$$, $$$u_i \neq v_i$$$
  • No two friend relations connect the same pair of two people.
Output

Output a single line with the minimum possible cost.

Examples
Input
5 3 4 2
1 5 6 9 10
2 10 1 10 10
1 2 1
3 4 8
4 5 9
Output
15
Input
6 9 5 3
1 4 6 7 11 12
4 3 9 5 7 6
2 6 3
5 2 7
3 2 2
4 5 6
1 5 6
4 6 4
4 3 9
1 6 1
3 1 6
Output
26