This page is still under construction.

Parts of this page are still being built. What you see may change.

Sugar Glider

Time limit2sMemory limit256 MB

Summary
Starting partway up tree 1, climb trees and glide between them while losing one meter of height per glide second to reach the top of tree N in minimum time.
Level

Hard8 of 10

Topics
Shortest path, Heap
Solved
No attempts yet

Problem

JOI the sugar glider lives in a forest with NN eucalyptus trees numbered 1 to NN. Tree ii has height HiH_i meters.

There are MM pairs of trees JOI can glide between directly, each with a fixed glide time. While gliding, height drops 1 meter per second. If current height is hh and a glide takes tt seconds, landing height is h−th-t. Gliding is impossible if h−th-t is below 0 or above the destination tree height.

JOI can climb or descend along a tree between 0 and that tree's height at 1 meter per second.

JOI starts at height XX on tree 1 and wants the top of tree NN (height HNH_N). Find the minimum time, or −1-1 if impossible.

Input

From standard input:

  • Line 1: integers NN, MM, XX
  • Next NN lines: height HiH_i of tree ii
  • Next MM lines: AjA_j, BjB_j, TjT_j describing a bidirectional glide of TjT_j seconds

Output

Print one integer: minimum seconds to reach the top of tree NN, or −1-1 if impossible.

Constraints

  • 2≤N≤100 0002 \le N \le 100\,000
  • 1≤M≤300 0001 \le M \le 300\,000
  • 1≤Hi≤1 000 000 0001 \le H_i \le 1\,000\,000\,000
  • 1≤Tj≤1 000 000 0001 \le T_j \le 1\,000\,000\,000
  • 0≤X≤H10 \le X \le H_1

Examples3

  1. Example 1

    Input
    5 5 0
50
100
25
30
10
1 2 10
2 5 50
2 4 20
4 3 1
5 4 20
    Expected output
    110

  2. Example 2

    Input
    2 1 0
1
1
1 2 100
    Expected output
    -1

  3. Example 3

    Input
    4 3 30
50
10
20
50
1 2 10
2 3 10
3 4 10
    Expected output
    100