Minimum Lane Driving Distance

You are given n lanes, each with a specified length, and m obstacles scattered across these lanes. Each obstacle is defined by a lane number x and covers an interval \([y, z]\) along that lane. Your task is to determine the minimum distance a car must travel in a given lane k in order to reach its eastern end while avoiding obstacles. Obstacles in lane k may overlap or be adjacent; in such cases, they must be merged into a single interval. If the merged obstacles block the entire lane (i.e. if the final merged interval reaches or exceeds the lane's total length), then the lane is considered completely blocked and you should output \(-1\). Otherwise, output the lane's length (which represents the minimum driving distance required).

Note: The input format guarantees that lanes are numbered from 1 through n. The car always starts at position 0 in lane k.

inputFormat

The first line of input contains three integers: \(n\), \(m\), and \(k\), where \(n\) is the number of lanes, \(m\) is the number of obstacles, and \(k\) is the lane you are interested in.

The second line contains \(n\) space-separated integers: \(L_1, L_2, \dots, L_n\), where \(L_i\) denotes the length of the \(i^{th}\) lane.

Each of the next \(m\) lines contains three integers: \(x\), \(y\), \(z\), indicating that there is an obstacle on lane \(x\) covering the interval \([y, z]\). Only the obstacles on lane \(k\) are considered when determining if the lane is fully blocked.

outputFormat

Output a single integer, which is the minimum distance that must be traveled in lane \(k\) to reach its eastern end. If the lane is completely blocked by obstacles, output \(-1\).

3 5 2
100 200 150
1 10 30
2 50 70
3 75 120
2 60 80
1 20 40

200