p01934 Dimension travel
problem

Dimension exists from $ 1 $ dimension to $ N $ dimension. AOR Ika can move between dimensions. Specifically, when AOR Ika is in the $ i $ dimension, she can move freely to the $ j $ dimension ($ i> j $), but in the $ k $ dimension ($ i <k $). You need to use magic to move to.

AOR Ika can use $ M $ types of magic and is numbered $ 1, 2, \ dots, M $. The $ i $ th magic allows you to move from the $ a_i $ dimension to the $ b_i $ dimension. This can only be used when you are in the $ a_i $ dimension.

When you go to the $ i $ dimension, you will receive a dimension-specific "curse of dimensionality". AOR Ika takes $ d_i $ damage due to the "curse of dimensionality" of the $ i $ dimension. If you receive the "curse of dimensionality" of the $ i $ dimension, you will not receive the "curse of dimensionality" of the $ j $ dimension ($ i> j $) forever.

Find the minimum total damage inflicted when AOR Ika moves from the $ s $ dimension to the $ t $ dimension. However, AOR Ika-chan has already received the "curse of dimensionality" of the $ s $ dimension, and we will not consider the damage. Also, AOR Ika is guaranteed to be able to go to the $ t $ dimension.



output

Output the minimum value of the total damage received by AOR Ika-chan. Also, output a line break at the end.

Example

Input

3 1 2 3
1 2 3
1 3


Output

3
```python
# AOJ 2834 Dimension travel
# Python3 2018.7.12 bal4u

INF = 0x7fffffff
import heapq
def dijkstra(V, to, start, goal):
	dist = [INF]*V
	Q = []
	dist[start] = 0
	heapq.heappush(Q, (0, start))
	while Q:
		t, s = heapq.heappop(Q)
		if s == goal: break
		if dist[s] < t: continue
		for e in to[s]:
			nt = t
			if e > s: nt += d[e]
			if dist[e] > nt:
				dist[e] = nt
				heapq.heappush(Q, (nt, e))
	return t

import sys
N, M, s, t = map(int, input().split())
s, t = s-1, t-1
if s >= t: print(0); sys.exit(0)
d = list(map(int, input().split()))
to = [[i-1] if i > 0 else [] for i in range(N)]
for i in range(M):
	a, b = map(int, input().split())
	to[a-1].append(b-1)
print(dijkstra(N, to, s, t))


```