Kozak Vus, the Secret of the Lady and the Witch#9089
Lady has finally decided to reveal her New Ultra-Secret Secret (NUSS) to Cossack Vus, but not without some complications. A witch has transformed Cossack Vus into a little man and challenged him to a game. Incidentally, many believe that the Lady herself is the witch, simply stalling for time.
The witch has placed the little man in a two-dimensional space—the first quadrant of the Cartesian coordinate system. In this space, there are horizontal segments (parallel to the -axis) and vertical lines (parallel to the -axis). Note that the segments have finite endpoints, while the lines are infinite.
Cossack Vus can be represented as a point. He can travel along the horizontal segments or vertical lines if he is located on them. Along the horizontal segments, he can only move to the right; along the vertical lines, he can move either up or down. Moreover, if he is at the rightmost endpoint of a horizontal segment, he can jump down and continue falling until he lands either on another horizontal segment or on the -axis. Initially, Cossack Vus stands at the leftmost endpoint of one of the horizontal segments. The game ends as soon as he reaches the -axis. His objective is to finish at the highest possible -coordinate.
The sooner the witch releases Vus, the sooner the Lady will unveil her NUSS. Help the Cossack by determining the greatest possible -coordinate at which he can finish the game.
The first line contains a single integer (1 \le n \le 100{,}000) — the number of horizontal segments.
The second line contains a single integer (1 \le m \le 100{,}000) — the number of vertical lines.
The third line contains a single integer (1 \le k \le n) — the index of the horizontal segment where Cossack Vus begins his journey.
Each of the next lines contains three integers x_l, x_r, (1 \le x_l < x_r \le 10^9, 1 \le y \le 10^9) — the left endpoint, right endpoint, and the -coordinate of a horizontal segment. It is guaranteed that no two horizontal segments overlap.
The next line contains integers (1 \le x \le 10^9) — the -coordinates of the vertical lines. All coordinates are distinct.
Output a single integer — the largest possible -coordinate where Cossack Vus can finish the game.
Example 1
Example 2