Problem H
Railroad Delivery

Di and John are playing a game about building railroads and making deliveries with trains to maximize profit. While Di is focused on winning the game, John is hopelessly lost and has decided to calculate the total potential money that could be made using a single train that starts from a hub.

There are $n$ train stations (numbered from 0 to $n-1$). Some stations are designated as hubs, and each station has goods worth a certain amount to deliver. There are $m$ railroad routes between the stations. Each route costs fuel for the train to travel, and the train has a maximum fuel capacity of $k$.

John must pick a starting hub for the train. The train can only travel between stations if there is a route connecting the stations and the fuel cost is less than or equal to the current remaining fuel. Routes are bidirectional, so if a route connects stations $u$ and $v$, the train can travel in either direction. Traveling along a route reduces the train’s fuel by the associated cost. To earn money, the train must visit a station to pick up the goods there and deliver them to any hub, earning money equal to the value of the goods. (The train has an infinite cargo capacity.) The train can also refuel at any hub to its maximum fuel capacity, and can do so an unlimited number of times at each hub. The train can also visit each station and travel along each route multiple times if needed.

Help John calculate the maximum profit that can be made with a single train and a starting hub that allows John to do so.

Input

The first line of input contains four integers $n$, $m$, $h$, and $k$, where:

• $n$ is the number of stations, $1 \le n \le 2\cdot 10^5$,

• $m$ is the number of routes between stations, $0 \le m \le n \cdot (n-1)/2$ and $m \le 4 \cdot 10^5$,

• $h$ is the number of hubs, $1 \le h \le n$,

• $k$ is the maximum fuel capacity, $2 \le k \le 10^6$.

The second line contains $n$ integers $p_0, p_1, \ldots , p_{n-1}$, where $p_i$ represents the value of goods at station $i$. $ 0 \le p_i \le 10^6$ for all $p_i$.

The third line contains $h$ integers $0 \le j_0 < j_1 < \ldots < j_{h-1} \le n-1$, where $j_i$ represents that station $j_i$ is a hub. It is guaranteed that all hubs are distinct and have goods with a value of 0.

The following $m$ lines contain three integers each $u, v,$ and $c$, representing a route between stations $u$ and $v$ with fuel cost $c$. $0 \le u < v \le n-1$, $1 \le c \le 10^6$, and there is at most one direct route between any two stations.

Output

The output depends on the maximum profit that can be made.

If the potential profit is greater than 0, output the maximum profit that can be made, followed by a starting hub for the train that allows John to achieve this maximum. If there are multiple such hubs, you may output any of them.

If John cannot make any profit at all, output NONE.

5 3 2 10
8 0 2 0 15
1 3
0 1 5
3 4 7
1 2 4

10 1

3 1 1 10
0 2 2
0
0 1 6

NONE