Problem Description

The dragon Evirir wrote $N$ pages about Olympiad in Informatics. For each integer $i = 0, 1, \ldots, N - 1$, there is exactly one page whose amount of knowledge is $i$. Evirir will bind these pages into a book. Formally, Evirir will choose a sequence $A_0, A_1, \ldots, A_{N - 1}$ of length $N$ consisting of pairwise distinct integers from $0$ to $N - 1$. Then, it will make a book such that page $i$ ($0 \le i \le N - 1$) has knowledge amount $A_i$.

Due to ancient dragon laws, the knowledge amounts of some pages are fixed. The law gives $N$ integers $B_0, B_1, \ldots, B_{N - 1}$. For each $0 \le i \le N - 1$, if $B_i \ne -1$, then it must hold that $A_i = B_i$. There are exactly $K$ values of $B_i$ with $B_i \ne -1$.

Evirir wants its $M$ students (numbered $0, 1, \ldots, M - 1$) to read the whole book. However, due to short attention spans, each student $i$ will only read pages $L_i, L_i + 1, \ldots, R_i$. A student's knowledge gain is defined as the sum of the knowledge amounts of the pages that the student reads.

If Evirir binds these pages in an optimal way, what is the maximum possible total knowledge gain of all students?

Input Format

The first line contains three integers $N$, $M$, and $K$, separated by spaces.

The second line contains $N$ integers $B_0, B_1, \ldots, B_{N - 1}$, separated by spaces.

The next $M$ lines follow. The $i$-th of them contains two integers $L_i$ and $R_i$, separated by spaces.

Output Format

Output one integer, the maximum possible total knowledge gain for all students.

5 2 5
3 4 1 0 2
0 2
1 4

15

5 3 2
2 -1 -1 1 -1
2 2
0 0
3 4

10

5 3 0
-1 -1 -1 -1 -1
1 3
4 4
0 4

20

Hint

Hint

$\underline{Sample\ 1}$

This sample applies to subtasks 1, 4, and 6.

Evirir wrote $N = 5$ pages, and there are $M = 2$ students. All $K = N$ pages are fixed.

• Student 0 reads pages 0 to 2 and gains $3 + 4 + 1 = 8$ knowledge.
• Student 1 reads pages 1 to 4 and gains $4 + 1 + 0 + 2 = 7$ knowledge.

Therefore, the total knowledge gain is $8 + 7 = 15$.

$\underline{Sample\ 2}$

This sample applies to subtasks 4 and 6.

There are $K = 2$ fixed pages: 0 and 3. One optimal binding is $A = [2, 0, 4, 1, 3]$.

• Student 0 reads pages 2 to 2 and gains $4$ knowledge.
• Student 1 reads pages 0 to 0 and gains $2$ knowledge.
• Student 2 reads pages 3 to 4 and gains $1 + 3 = 4$ knowledge.

The total knowledge gain is $4 + 2 + 4 = 10$. Note that there may be other optimal bindings.

Some examples of $A$ that Evirir cannot choose:

• $A = [4, 0, 3, 1, 2]$: page 0 is fixed as $B_0 = 2$, but here $A_0 = 4$.
• $A = [2, 4, 4, 1, 4]$: the knowledge amounts are not pairwise distinct.
• $A = [2, 3, 5, 1, 4]$: the knowledge amounts must be between 0 and $N - 1$.

$\underline{Sample\ 3}$

This sample applies to subtasks 3, 4, and 6.

Since $K = 0$, no page has a fixed knowledge amount. One optimal binding is $A = [0, 4, 2, 1, 3]$.

• Student 0 reads pages 1 to 3 and gains $4 + 2 + 1 = 7$ knowledge.
• Student 1 reads pages 4 to 4 and gains $3$ knowledge.
• Student 2 reads pages 0 to 4 and gains $0 + 4 + 2 + 1 + 3 = 10$ knowledge.

The total knowledge gain is $7 + 3 + 10 = 20$.

Scoring

For all testdata, the input satisfies the following constraints:

• $1 \le N \le 5 \cdot 10^5$
• $1 \le M \le 10^5$
• $0 \le K \le N$
• For all $0 \le i \le N - 1$, $-1 \le B_i \le N - 1$
• There are exactly $K$ indices $i$ such that $B_i \ne -1$
• All fixed values are pairwise distinct: if $B_i \ne -1$ and $B_j \ne -1$ and $i \ne j$, then $B_i \ne B_j$
• For all $0 \le i \le M - 1$, $0 \le L_i \le R_i \le N - 1$

Translated by ChatGPT 5