Zxr960115 is owner of a large farm. He feeds m cute cats and employs p feeders. There's a straight road across the farm and n hills along the road, numbered from 1 to n from left to right. The distance between hill i and (i - 1) is di meters. The feeders live in hill 1.

One day, the cats went out to play. Cat i went on a trip to hill hi, finished its trip at time ti, and then waited at hill hi for a feeder. The feeders must take all the cats. Each feeder goes straightly from hill 1 to n without waiting at a hill and takes all the waiting cats at each hill away. Feeders walk at a speed of 1 meter per unit time and are strong enough to take as many cats as they want.

For example, suppose we have two hills (d2 = 1) and one cat that finished its trip at time 3 at hill 2 (h1 = 2). Then if the feeder leaves hill 1 at time 2 or at time 3, he can take this cat, but if he leaves hill 1 at time 1 he can't take it. If the feeder leaves hill 1 at time 2, the cat waits him for 0 time units, if the feeder leaves hill 1 at time 3, the cat waits him for 1 time units.

Your task is to schedule the time leaving from hill 1 for each feeder so that the sum of the waiting time of all cats is minimized.

Input

The first line of the input contains three integers n, m, p (2 ≤ n ≤ 105, 1 ≤ m ≤ 105, 1 ≤ p ≤ 100).

The second line contains n - 1 positive integers d2, d3, ..., dn (1 ≤ di < 104).

Each of the next m lines contains two integers hi and ti (1 ≤ hi ≤ n, 0 ≤ ti ≤ 109).

Output

Output an integer, the minimum sum of waiting time of all cats.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

4 6 2
1 3 5
1 0
2 1
4 9
1 10
2 10
3 12


Output

3
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;


public class D {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
	public void solve() throws IOException {				
		int N = nextInt();
		int M = nextInt();
		int P = nextInt();
		long[] D = new long[N-1];
		for(int i = 0; i < N-1; i++)
			D[i] = nextInt();
		
		long[] distance = new long[N];
		distance[0] = 0;
		for(int i = 1; i < N; i++)
			distance[i] = distance[i-1] + D[i-1];
		
		long[] cats = new long[M+1];
		cats[0] = Long.MIN_VALUE;
		for(int i = 1; i <= M; i++){
			int H = nextInt()-1;
			long T = nextInt();
			cats[i] = T - distance[H];
		}
		shuffleArray(cats);
		Arrays.sort(cats);
		
		if( P >= M ){
			out.println(0); return;
		}
		
		long[] cum = new long[M+1];
		cum[1] = cats[1];
		for(int i = 2; i <= M; i++){
			cum[i] = cum[i-1] + cats[i]; 
		}
		
		long[] dp = new long[M+1];
		long[] old = new long[M+1];
		long INF = Long.MAX_VALUE/2;
		for(int i = 0; i <= P; i++)
			Arrays.fill(dp, INF);
		dp[0] = 0;

		for(int p = 0; p < P; p++){
			long[] tmp = dp;
			dp = old;
			old = tmp;
//			Line[] lines = new Line[M+1];
			long[][] lines = new long[M+1][];
			int head = 0;
			int tail = 0;
			
			for(int j = 0; j <= M; j++){
//				Line newLine = new Line( (long)-j, dp[p][j] + cum[j], j );
				long[] newLine = new long[]{ (long)-j, old[j] + cum[j], j };
				
//				while( tail > head+1 && getIntersect(lines[tail-2], newLine) < getIntersect(lines[tail-1], lines[tail-2] ) )
				while( tail > head+1 && compareIntersect( lines[tail-2], lines[tail-1], newLine ))
					tail--;
				lines[tail++] = newLine;
				
				while( head < tail-1 && getPartialCost(old, cats, cum, j, (int)lines[head][2]) > getPartialCost(old, cats, cum, j, (int)lines[head+1][2] ) )
					head++;				
				dp[j] = getCost(old, cats, cum, j, (int)lines[head][2] );
			}
		}		
		out.println( dp[M] );		
	}

	public boolean compareIntersect(long[] line1, long[] line2, long[] line3){
		return (line1[1] - line3[1]) * (line2[0] - line1[0]) < (line1[1] - line2[1]) * (line3[0] - line1[0]);
	}
	
	public double getIntersect(long[] line1, long[] line2){
		return ( (double)(line1[1] - line2[1]) / (double)(line2[0] - line1[0]) );  
	}
	
	public long getCost(long[]dp, long[]cats, long[]cum, int j, int i){
		return dp[i] + cats[j]*(j-i) - (cum[j] - cum[i]);
	}
	
	public long getPartialCost(long[]dp, long[]cats, long[]cum, int j, int i){
		return dp[i] - cats[j]*i + cum[i];
	}
	
	public void shuffleArray(long[] arr) {
        Random rnd = new Random();
        for (int i = arr.length - 1; i >= 0; i--) {
            int pos = rnd.nextInt(i + 1);
            long temp = arr[i];
            arr[i] = arr[pos];
            arr[pos] = temp;
        }
    }
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new D().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}