Problem Description

Takahashi-kun receives $ M $ assignments over $ N $ days. He needs to submit at least $ K $ assignments; otherwise, he will fail the year.
The distribution date for the $ i $-th assignment is $ S_i $, and the deadline is $ E_i $. He can submit the assignment if he completes it from $ S_i $ to $ E_i $ (including both days).

Each day has a "dislike to do" value. The "dislike to do" value for day $ i $ is $ X_i $.
Takahashi-kun can choose to either "do one assignment" or "do no assignment" on each day. He cannot do more than one assignment per day.
Find the minimum total "dislike to do" value for the days he does the assignments while completing at least $ K $ assignments. Output the total "dislike to do" value.

If it is impossible to complete at least $ K $ assignments, output $ -1 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ K $ $ X_1 $ $ X_2 $ $ X_3 $ ... $ X_N $ $ S_1 $ $ E_1 $ $ S_2 $ $ E_2 $ $ S_3 $ $ E_3 $ ... $ S_M $ $ E_M $

Output Format

None

Sample Input and Output

Sample Input #1

4 3 2
5 6 3 7
1 1
2 3
3 4

Sample Output #1

8

Sample Input #2

5 5 5
8 6 9 1 20
1 2
3 4
5 5
4 5
3 5

Sample Output #2

-1

Notes/Hints

Constraints

• $1 \leq N \leq 1000$
• $1 \leq K \leq M \leq 1000$
• $1 \leq S_i \leq E_i \leq N$
• $1 \leq X_i \leq 10^{9}$
• All inputs are integers

Subtasks

Subtask $ 1 $ [$ 12 $ points]
The input satisfies the following conditions:

• $N \leq 6$
• $K \leq 6$

Subtask $ 2 $ [$ 18 $ points]
The input satisfies the following conditions:

• $N \leq 15$
• $M \leq 80$

Subtask $ 3 $ [$ 30 $ points]
The input satisfies the following conditions:

• $ S_i = 1 $ ($1 \leq i \leq M$)

Subtask $ 4 $ [$ 24 $ points]
The input satisfies the following conditions:

• $N \leq 80$
• $M \leq 80$

Subtask $ 5 $ [$ 16 $ points]

• No additional constraints.

见题面 Input 部分

见题面 Output 部分