#include <bits/stdc++.h>
using namespace std;

int n, m, q, a, b, v[55], w[55], cnt, dp[55][55];

pair <int, int> p[55];

int main(){
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++) cin >> a >> b, p[i] = make_pair(a, b);
    sort(p + 1, p + 1 + n);
    for(int i = 1; i <= m; i++) cin >> v[i];
    while(q--){
        cin >> a >> b, cnt = 0;
        for(int i = 1; i <= m; i++) if(i > b || i < a) w[++cnt] = v[i];
        sort(w + 1, w + 1 + cnt);
        for(int i = 1; i <= cnt; i++)
            for(int j = 1; j <= n; j++){
                if(p[j].first > w[i]){
                    dp[i][j] = dp[i][j - 1];
                    continue;
                }
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - 1] + p[j].second);
            }
        cout << dp[cnt][n] << endl;
        memset(dp, 0, sizeof(dp));
    }
    return 0;
}

/**
*    author:  tomo0608
*    created: 20.02.2021 21:39:59
**/

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
template <class T> using V = vector<T>;
template <class T> using VV = V<V<T>>;
typedef pair<int,int> pii;
typedef pair<long long, long long> pll;

#define all(x) x.begin(),x.end()
#define rep2(i, m, n) for (int i = (m); i < (n); ++i)
#define rep(i, n) rep2(i, 0, n)
#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)
#define drep(i, n) drep2(i, n, 0)
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
template<class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T> >;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a>b) { a=b; return 1; } return 0; }
template<class T1, class T2> istream &operator>>(istream &is, pair<T1, T2> &p) { is >> p.first >> p.second; return is; }
template<class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &p) { os << '(' << p.first << ", " << p.second << ')'; return os; }
template<class T> istream &operator>>(istream &is, vector<T> &v) { for (auto &e : v) is >> e; return is; }
template<class T> ostream &operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<typename T> ostream& operator << (ostream& os, set<T>& set_var) {os << "{"; for (auto itr = set_var.begin(); itr != set_var.end(); itr++) {os << *itr;++itr;if(itr != set_var.end()) os << ", ";itr--;}os << "}";return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, map<T, U> &map_var) {os << "{";for(auto itr = map_var.begin(); itr != map_var.end(); itr++) {os << *itr;itr++;if (itr != map_var.end()) os << ", ";itr--;}os << "}";return os;}
template<class T> inline int count_between(vector<T> &a, T l, T r) { return lower_bound(all(a), r) - lower_bound(all(a), l); } // [l, r)
#define pb push_back
#define eb emplace_back
#define elif else if
#define mp make_pair
#define bit(n, k) ((n >> k) & 1) /*nのk bit目*/
template<typename T> T gcd(T x, T y){if(x%y == 0)return y;return gcd(y, x%y);}
template<typename T> T gcd(vector<T> a){T res = a[0];for(auto &x: a)res = gcd(res, x);return res;}
template <typename T>T mypow(T x, ll n){T ret = 1;while(n > 0){if(n & 1)(ret *= x);(x *= x);n >>= 1;}return ret;}
#define endl '\n'
int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1};
int dy[8] = {0, 1, 0, -1, 1, -1, -1, 1};

// Primality test
class Prime {
    public:
    const int N;
    vector<int> min_prime;
    vector<int> primes;
    Prime(int size): N(size), min_prime(N+1){
        rep(i,N+1)min_prime[i] = i;
        min_prime[0] = -1;
        min_prime[1] = -1;
        for(int i = 2;i<=N;i++){
            if(min_prime[i]!=i)continue;
            primes.push_back(i);
            int tmp = 2*i;
            while(tmp <= N){
                if(min_prime[tmp]==tmp)min_prime[tmp] = i;
                tmp += i;
            }
        }
    }
    bool check(int x){ return min_prime[x] == x;}
};

void solve(){
    ll n,x;cin >> n >> x;
    V<ll> a(n);cin >> a;
    ll ans = x - *max_element(all(a));
    rep2(S,1, n+1){
        VV<ll> dp(S+1, V<ll>(S, -1));
        dp[0][0] = 0;
        rep(i,n){
            VV<ll> new_dp(S+1, V<ll>(S,-1));
            rep(j,S+1)rep(k,S){
                if(dp[j][k] != -1){
                    if(j < S)chmax(new_dp[j+1][(k + a[i])%S], dp[j][k] + a[i]);
                    chmax(new_dp[j][k], dp[j][k]);
                }
            }
            dp = new_dp;
        }
        if(dp[S][x%S] != -1){
            chmin(ans, (x - dp[S][x%S])/S);
        }
    }
    cout << ans << endl;
}

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << setprecision(20);
    int codeforces = 1;
    //cin >> codeforces;
    while(codeforces--){
        solve();
    }
    return 0;
}