We’re preparing your current view and syncing the latest data.
There are several cities located along a number line at distinct integer coordinates. Some segments on this number line are blocked and cannot be used for road construction. The task is to connect all cities with roads of minimum total length without constructing roads on the blocked segments. Roads can only be built on the unblocked segments between cities. Find the minimum total length of roads required to connect all cities, or determine that it's impossible.
The first line contains three integers n, m, and k — the number of cities, the total length of the number line, and the number of blocked segments respectively. The second line contains n distinct integers ai — the coordinates of the cities. Each of the next k lines contains two integers l and r, representing a blocked segment from l to r (inclusive).
Print the minimum total length of roads needed to connect all cities considering the blocked segments, or -1 if it is impossible to connect them all.
1 ≤ n ≤ 1000 1 ≤ m ≤ 10^9 0 ≤ k ≤ 1000 All ai are distinct integers between 1 and m Blocked segments are within 1 to m
Example 1
Input
3 10 1 2 6 8 5 7
Output
6
Explanation
Cities at 2, 6, and 8. The segment from 5 to 7 is blocked. We can build roads between 2 and 6 (length 4), but cannot connect 6 and 8 through the blocked segment. So, roads must be built to connect 2 to 6 and then 6 to 8 skipping the blocked area if possible. Since 6 to 8 is blocked partially, they cannot be connected directly, so total length is 4 + 2 = 6.