There are $n$ shovels in the nearby shop. The $i$-th shovel costs $a_i$ bourles.

Misha has to buy exactly $k$ shovels. Each shovel can be bought no more than once.

Misha can buy shovels by several purchases. During one purchase he can choose any subset of remaining (non-bought) shovels and buy this subset.

There are also $m$ special offers in the shop. The $j$-th of them is given as a pair $(x_j, y_j)$, and it means that if Misha buys exactly $x_j$ shovels during one purchase then $y_j$ most cheapest of them are for free (i.e. he will not pay for $y_j$ most cheapest shovels during the current purchase).

Misha can use any offer any (possibly, zero) number of times, but he cannot use more than one offer during one purchase (but he can buy shovels without using any offers).

Your task is to calculate the minimum cost of buying $k$ shovels, if Misha buys them optimally.


-----Input-----

The first line of the input contains three integers $n, m$ and $k$ ($1 \le n, m \le 2 \cdot 10^5, 1 \le k \le min(n, 2000)$) — the number of shovels in the shop, the number of special offers and the number of shovels Misha has to buy, correspondingly.

The second line of the input contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 2 \cdot 10^5$), where $a_i$ is the cost of the $i$-th shovel.

The next $m$ lines contain special offers. The $j$-th of them is given as a pair of integers $(x_i, y_i)$ ($1 \le y_i \le x_i \le n$) and means that if Misha buys exactly $x_i$ shovels during some purchase, then he can take $y_i$ most cheapest of them for free.


-----Output-----

Print one integer — the minimum cost of buying $k$ shovels if Misha buys them optimally.


-----Examples-----
Input
7 4 5
2 5 4 2 6 3 1
2 1
6 5
2 1
3 1

Output
7

Input
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7

Output
17

Input
5 1 4
2 5 7 4 6
5 4

Output
17



-----Note-----

In the first example Misha can buy shovels on positions $1$ and $4$ (both with costs $2$) during the first purchase and get one of them for free using the first or the third special offer. And then he can buy shovels on positions $3$ and $6$ (with costs $4$ and $3$) during the second purchase and get the second one for free using the first or the third special offer. Then he can buy the shovel on a position $7$ with cost $1$. So the total cost is $4 + 2 + 1 = 7$.

In the second example Misha can buy shovels on positions $1$, $2$, $3$, $4$ and $8$ (costs are $6$, $8$, $5$, $1$ and $2$) and get three cheapest (with costs $5$, $1$ and $2$) for free. And then he can buy shovels on positions $6$, $7$ and $9$ (all with costs $1$) without using any special offers. So the total cost is $6 + 8 + 1 + 1 + 1 = 17$.

In the third example Misha can buy four cheapest shovels without using any special offers and get the total cost $17$.

Difficulty: introductory

Starter code:

Solutions:
import sys
import copy
input = sys.stdin.readline

n,m,k=list(map(int,input().split()))
A=list(map(int,input().split()))
SHOP=[list(map(int,input().split())) for i in range(m)]

A=sorted(A)[:k]
A=A[::-1]

SHOP.sort(key=lambda x:x[0])

from itertools import accumulate 

DP=[0]+list(accumulate(A))
SUM=copy.deepcopy(DP)

for i in range(k+1):
    for x,y in SHOP:
        if x>i:
            break
        DP[i]=min(DP[i],DP[i-x]+SUM[i]-SUM[i-x]-SUM[i]+SUM[i-y],DP[i-1]+A[i-1])

print(DP[-1])
        


IN = input
rint = lambda: int(IN())
rmint = lambda: list(map(int, IN().split()))
rlist = lambda: list(rmint())

n, m, k = rmint()
a = rlist()
t = []
for i in range(m):
    x, y = rmint()
    t.append((x, y))
t.sort()
a.sort()
pr = [0]
for i in a: pr.append(pr[-1] + i)
f = 4096 * [0]


def s(l, r):
    if l > r: return 0
    else: return pr[r + 1] - pr[l]


ans = s(0, k-1)


def upd(x, y):
    nonlocal ans
    f[x] = min(f[x], y)
    ans = min(ans, y + s(x, k - 1))


for i in range(1, k + 1):
    f[i] = f[i - 1] + a[i - 1]
    for p in t:
        x, y = p
        if i - x < 0: break
        upd(i, f[i - x] + s(i - x + y, i - 1))

print(ans)


N, M, K = list(map(int, input().split()))
A = sorted([int(a) for a in input().split()])[:K][::-1]
B = [0]
for a in A:
    B.append(B[-1]+a)
X = [0] * (K+1)
for _ in range(M):
    x, y = list(map(int, input().split()))
    if x <= K:
        X[x] = max(X[x], y)

Y = [0] * (K+1)

for i in range(1, K+1):
    mi = 10**100
    for j in range(1, i+1):
        s = Y[i-j] + B[i-X[j]] - B[i-j]
        mi = min(mi, s)
    
    Y[i] = mi

print(Y[K])


n,m,k = list(map(int,input().split()))
ai = list(map(int,input().split()))
ar = [0] * k
for i in range(m):
    x,y = list(map(int,input().split()))
    x -= 1
    if x < k:
        ar[x] = max(ar[x],y)
ai.sort()
big = 10**9
ar2 = [big] * (k+1)
ar3 = [0] * (k+1)
ar3[0] = 0
for i in range(1,k+1):
    ar3[i] = ar3[i-1] + ai[i-1]
ar2[k] = 0
for i in range(k,0,-1):
    for j in range(i):
        ar2[i-j-1] = min(ar2[i-j-1],ar2[i] + ar3[i] - ar3[i - (j + 1 - ar[j])])
print(ar2[0])


from collections import defaultdict
from heapq import heapify, heappop
n, m, k = map(int, input().split())
items = list(map(int, input().split()))
heapify(items)
items2 = []
for i in range(k):
    items2 += [heappop(items)]
items = items2
offers = defaultdict(lambda :0)
for i in range(m):
    a, b = map(int, input().split())
    if a <= k:
        offers[a] = max(offers[a], b)
dp = [1e20] * (k + 1)
dp[0] = 0
prefix = [0]
for i in items:
    prefix += [prefix[-1] + i]
for i in range(1, k + 1):
    for j in range(1, i + 1):
        b = offers[j]
        # buy j items, b free
        dp[i] = min(dp[i], dp[i - j] + prefix[i] - prefix[i - j + b])
print(dp[-1])

N, M, K = map(int, input().split())
A = sorted([int(a) for a in input().split()])[:K][::-1]
B = [0]
for a in A:
    B.append(B[-1]+a)
X = [0] * (K+1)
for _ in range(M):
    x, y = map(int, input().split())
    if x <= K:
        X[x] = max(X[x], y)
Y = [0] * (K+1)
for i in range(1, K+1):
    mi = 10**100
    for j in range(1, i+1):
        s = Y[i-j] + B[i-X[j]] - B[i-j]
        mi = min(mi, s)
    Y[i] = mi
print(Y[K])

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Codeforces Round #552 (Div. 3)

Problem F. Shovels Shop

:author:         Kitchen Tong
:mail:    kctong529@gmail.com

Please feel free to contact me if you have any question
regarding the implementation below.
"""

__version__ = '2.0'
__date__ = '2019-04-17'

import sys
from heapq import heappush, heappop


def buy_shovels(k, shovels, discounts):
    if 1 not in discounts:
        discounts[1] = 0
    accums = [0]
    for s in shovels:
        accums.append(s + accums[-1])
    for i in range(k):
        for x, y in list(discounts.items()):
            if i + x > k:
                continue
            perhaps = accums[i] + sum(shovels[i+y:i+x])
            accums[i+x] = min(accums[i+x], perhaps)
    return accums[-1]


def main(argv=None):
    n, m, k = list(map(int, input().split()))
    costs = list(map(int, input().split()))
    discounts = dict()
    for line in range(m):
        x, y = list(map(int, input().split()))
        if x > k:
            # this discount is useless as we can't buy more than k
            continue
        if x not in discounts:
            discounts[x] = y
        else:
            discounts[x] = max(discounts[x], y)
    print(buy_shovels(k, sorted(costs)[:k], discounts))
    return 0


def __starting_point():
    STATUS = main()
    return(STATUS)


__starting_point()

from collections import defaultdict


def buy(k, sums, offset, discounts):
    return sums[offset + k] - sums[offset + discounts[k]]


def main():
    n, m, k = list(map(int, input().split()))
    prices = sorted(list(map(int, input().split())))[:k]
    sums = [0] * (k + 1)
    for i in range(1, k + 1):
        sums[i] = sums[i - 1] + prices[i - 1]

    discounts = defaultdict(int)
    for _ in range(m):
        x, y = tuple(map(int, input().split()))
        discounts[x] = max(discounts[x], y)

    d = [0] * (k + 1)

    for i in range(1, k + 1):
        d[i] = buy(i, sums, 0, discounts)

        for j in range(1, i + 1):
            d[i] = min(d[i], d[j] + buy(i - j, sums, j, discounts))

    print(d[k])


def __starting_point():
    main()

__starting_point()

'''input
9 4 8
6 8 5 1 8 1 1 2 1
9 2
8 4
5 3
9 7
'''
from sys import stdin
import math
from copy import deepcopy
from collections import defaultdict


def process_offer(offers):
	aux = []
	for i in offers:
		temp = offers[i]
		temp.sort()
		aux.append([i, temp[-1]])

	aux = sorted(aux, key = lambda x: x[0])
	return aux


def make(first, second):
	return str(first) + ' ' + str(second)


def brute(arr, dp, offers, index, remain):
	#print(index, remain)
	# base case:
	if remain == 0:
		return 0

	if make(index, remain) in dp:
		return dp[make(index, remain)]

	min_cost = arr[index] + brute(arr, dp, offers, index + 1, remain - 1)
	#print(min_cost)
	for i in range(len(offers)):
		cost = 0
		if offers[i][0] <= remain:
			free = offers[i][1]
			for  j in range(index + free, index + offers[i][0]):
				cost += arr[j]
			cost += brute(arr, dp, offers, index + offers[i][0], remain - offers[i][0])
			min_cost = min(min_cost, cost)
		else:
			break
	dp[make(index, remain)] = min_cost
	return min_cost



# main starts
n, m, k = list(map(int, stdin.readline().split()))
arr = list(map(int, stdin.readline().split()))
arr.sort()
offers = defaultdict(list)
for _ in range(m):
	x, y = list(map(int, stdin.readline().split()))
	offers[x].append(y)

offers = process_offer(offers)
dp = dict()
print(brute(arr, dp, offers, 0, k))
#print(dp)



n, m, k = list(map(int, input().split()))
a = list(map(int, input().split()))
a = sorted(a)
a = a[:k]
d = [(1, 0)]
for i in range(m):
    x, y = list(map(int, input().split()))
    if x > k:
        continue
    d.append((x, y))
d = sorted(d)

s = [0] * (k + 1)
s[1] = a[0]
for i in range(1, k + 1):
    s[i] = s[i - 1] + a[i - 1]
INF = float('inf')
dp = [INF] * (k + 1)
dp[0] = 0
for i in range(k + 1):
    for j in range(len(d)):
        x, y = d[j]
        if i + x <= k:
            dp[i + x] = min(dp[i + x], dp[i] + s[i + x] - s[i + y])
        else:
            break

print(dp[k])



from sys import stdin
import math
from copy import deepcopy
from collections import defaultdict
def process_offer(offers):
	aux = []
	for i in offers:
		temp = offers[i]
		temp.sort()
		aux.append([i, temp[-1]])
	aux = sorted(aux, key = lambda x: x[0])
	return aux
def make(first, second):
	return str(first) + ' ' + str(second)

def brute(arr, dp, offers, index, remain):
	#print(index, remain)
	# base case:
	if remain == 0:
		return 0
	if make(index, remain) in dp:
		return dp[make(index, remain)]
	min_cost = arr[index] + brute(arr, dp, offers, index + 1, remain - 1)
	#print(min_cost)
	for i in range(len(offers)):
		cost = 0
		if offers[i][0] <= remain:
			free = offers[i][1]
			for  j in range(index + free, index + offers[i][0]):
				cost += arr[j]
			cost += brute(arr, dp, offers, index + offers[i][0], remain - offers[i][0])
			min_cost = min(min_cost, cost)
		else:
			break
	dp[make(index, remain)] = min_cost
	return min_cost
n, m, k = list(map(int, stdin.readline().split()))
arr = list(map(int, stdin.readline().split()))
arr.sort()
offers = defaultdict(list)
for _ in range(m):
	x, y = list(map(int, stdin.readline().split()))
	offers[x].append(y)

offers = process_offer(offers)
dp = dict()
print(brute(arr, dp, offers, 0, k))

from sys import stdin, stdout

n, m, k = tuple(map(lambda x: int(x), stdin.readline().split()))
a = stdin.readline().split()
for i in range(len(a)):
    a[i] = int(a[i])
prefix_sum = []
a = sorted(a, key=lambda x: x)
for x in a:
    if prefix_sum:
        prefix_sum.append(prefix_sum[-1] + x)
    else:
        prefix_sum.append(x)

offers = {}
for i in range(m):
    x, y = stdin.readline().split()
    x = int(x)
    y = int(y)
    if x not in offers or y > offers[x]:
        offers[x] = y


answer = []
for i in range(k):
    if i == 0:
        if 1 in offers and offers[1] > 0:
            answer.append(0)
        else:
            answer.append(a[0])
        continue
    answer.append(400000002)
    for j in range(i):
        cursum = answer[j]
        answer[i] = min(answer[i], answer[j] + prefix_sum[i] - prefix_sum[j + (offers[i - j] if (i - j) in offers else 0)])
    answer[i] = min(answer[i], prefix_sum[i] if (i+1) not in offers else (-prefix_sum[offers[i+1]-1] + prefix_sum[i]))


print(answer[k-1])

#Bhargey Mehta (Sophomore)
#DA-IICT, Gandhinagar
import sys, math, queue
#sys.stdin = open("input.txt", "r")
MOD = 10**9+7

n, m, k = map(int, input().split())
a = sorted(map(int, input().split()))
a = a[:k]
ps = [0]
for i in range(k):
    ps.append(ps[-1]+a[i])
bf = []
temp = [0 for i in range(k+1)]
for i in range(m):
    b, f = map(int, input().split())
    if b <= k:
        temp[b] = max(temp[b], f)
for i in range(1, k+1):
    if temp[i] != 0:
        bf.append((i, temp[i]))
bf = [(1, 0)] + sorted(bf, key = lambda x: (x[0]-x[1], b))

dp = [[-1 for i in range(len(bf))] for i in range(k+1)]

for i in range(len(bf)): dp[0][i] = 0
for i in range(1, k+1): dp[i][0] = ps[i]

for i in range(1, k+1):
    for j in range(1, len(bf)):
        dp[i][j] = dp[i][j-1]
        b = bf[j][0]
        f = bf[j][1]
        if b <= i:
            dp[i][j] = min(dp[i][j], dp[i-b][len(bf)-1]+ps[i]-ps[i-b+f])

print(dp[k][len(bf)-1])

# http://codeforces.com/contest/1154/problem/F
# Explain: https://codeforces.com/blog/entry/66586?locale=en
from collections import defaultdict


def input2int():
    return list(map(int, input().split()))


n, m, k = input2int()
cost = list(input2int())
cost = sorted(cost)[:k]
# cost.reverse()
# print(cost)

preSum = defaultdict(int)
for i in range(k):
    preSum[i] = preSum[i - 1] + cost[i]
preSum[k] = preSum[k - 1]
# print(preSum)

offer = []
for i in range(m):
    x, y = input2int()
    if x <= k:
        offer.append((x, y))

# print(offer)

dp = defaultdict(lambda: int(1e9))
dp[0] = 0

for i in range(k + 1):
    if i < k:
        dp[i + 1] = min(dp[i] + cost[i], dp[i + 1])
    for _ in offer:
        x, y = _
        # print("i: {}, x: {}, y: {}".format(i, x, y))
        if i + x > k:
            continue
        # print('sum: {}'.format(preSum[i + x] - preSum[i + y]))
        dp[i + x] = min(dp[i + x], dp[i] + preSum[i + x - 1] - preSum[i + y - 1])
        # print(dp)

# print(dp)
print(dp[k])


import math
from collections import defaultdict
import sys
input = sys.stdin.readline


def main():
    n, m, k = list(map(int, input().split()))
    a = sorted(list(map(int, input().split())))
    pref = [0] + a.copy()
    for i in range(1, n+1):
        pref[i] += pref[i-1]

    def getPref(start, end):
        if start > end:
            return 0
        if start == 0:
            return pref[end]
        return pref[end] - pref[start-1]

    offers = {}
    for i in range(m):
        a, b = list(map(int, input().split()))
        if a not in offers:
            offers[a] = b
        else:
            if b > offers[a]:
                offers[a] = b

    if 1 not in offers:
        offers[1] = 0

    dp = [math.inf] * (k+1)
    dp[0] = 0
    for i in range(0, k+1):
        for j in offers:
            if i + j <= k:
                dp[i+j] = min(dp[i+j], dp[i] + getPref(i + offers[j]+1, i+j))

    print(dp[k])


def __starting_point():
    main()

__starting_point()

from audioop import reverse
n, m, k = list(map(int,input().split()))
price = list(map(int,input().split()))
offer = [0] * (k + 1)
for i in range(m):
    x , y = list(map(int,input().split()))
    if x <= k:
        offer[x] = max(offer[x] , y)
price.sort()
for _ in range(n-k):
    price.pop()
price.sort(reverse=True)
prep = [0] * (k + 1)
for i in range(k):
    prep[i + 1] = prep[i] + price[i] 
min_price = [prep[k]] * (k + 1)
min_price[0] = 0
for i in range(k):
    min_price[i + 1] = min(min_price[i + 1],min_price[i] + price[i])
    for j in range(1 , k + 1):
        if offer[j] == 0:
            continue
        if i + j > k:
            break
        min_price[i + j] = min(min_price[i + j] , min_price[i] + prep[i + j - offer[j]] -prep[i])
print(min_price[k])        
    
    
    
    
    
    
    
    
    
    
    


n, m, k = (int(i) for i in input().split())
cost = sorted([int(i) for i in input().split()])[:k] + [0]

discount = [0] * n
for i in range(m):
    a, b = (int(j) for j in input().split())
    discount[a - 1] = max(discount[a - 1], b)

S = [0] * (k + 1)
for i in range(k):
    S[i] = cost[i] + S[i - 1]
    cost[i] += cost[i - 1]    
    for j in range(i + 1):
        S[i] = min(S[i], S[j - 1] + cost[i] - cost[j - 1 + discount[i - j]])
print(S[k - 1])

import sys

dp = []
sum = []
INF = sys.maxsize / 2

def sum_range(a, b):
	if a == 0:
		return sum[b]
	return sum[b] - sum[a - 1]

def rec(pos, sale, n, k):
	if k == 0:
		return 0
	if dp[k] != -1:
		return dp[k]
	
	res = INF
	for x in range(1, k + 1):
		if sale[x] != -1:
			res = min(res, rec(pos + x, sale, n, k - x) + sum_range(pos + sale[x], pos + x - 1))
	dp[k] = res
	return res

inp = [int(x) for x in sys.stdin.read().split()]

n, m, k = inp[0], inp[1], inp[2]
inp_idx = 3

a = []
for _ in range(n):
	a.append(inp[inp_idx])
	inp_idx += 1

sale = [-1] * (k + 1)
sale[1] = 0
for _ in range(m):
	x, y = inp[inp_idx], inp[inp_idx + 1]
	inp_idx += 2
	if x > k:
		continue
	sale[x] = max(sale[x], y)
	
a.sort()

sum = [0] * n
sum[0] = a[0]
for i in range(1, n):
	sum[i] = sum[i - 1] + a[i]

dp = [-1] * (k + 1)
cost = rec(0, sale, n, k)
print(cost)

n,m,k=map(int,input().split())
arr=list(map(int,input().split()))
offer=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr)
arr=arr[:k]
arr=arr[::-1]
acum=[0]
for i in range(k):
    acum.append(acum[-1]+arr[i])
dp=[acum[i] for i in range(k+1)]
for x,y in offer:
    if x>k:
        continue
    for i in range(x,k+1):
        dp[i]=min(dp[i],dp[i-x]+(acum[i]-acum[i-x])-(acum[i]-acum[i-y]))
    tmp=dp[0]
    for i in range(1,k+1):
        tmp=min(tmp,dp[i-1])+arr[i-1]
        dp[i]=min(dp[i],tmp)
for x,y in offer:
    if x>k:
        continue
    for i in range(x,k+1):
        dp[i]=min(dp[i],dp[i-x]+(acum[i]-acum[i-x])-(acum[i]-acum[i-y]))
    tmp=dp[0]
    for i in range(1,k+1):
        tmp=min(tmp,dp[i-1])+arr[i-1]
        dp[i]=min(dp[i],tmp)
print(dp[k])