Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define ll long long
- #define F first
- #define S second
- typedef pair<int, int> ii;
- typedef vector<int> vi;
- inline ll gi() {
- ll x=0,f=1;
- char ch=getchar();
- while(!isdigit(ch))f^=ch=='-',ch=getchar();
- while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
- return f?x:-x;
- }
- bool sortp(const vector<int> &a, const vector<int> &b) {
- return a[1]<b[1];
- }
- int milk[100005], msuffix[100005], rent[100005], rsuffix[100005];
- vector<vi> store;
- int main() {
- #ifndef HOME
- freopen("rental.in", "r", stdin);
- freopen("rental.out", "w", stdout);
- #endif
- int n=gi(), m=gi(), r=gi();
- for(int i=0; i<n; i++) milk[i]=gi();
- for(int i=0; i<m; i++) {
- vi s;
- for(int j=0; j<2; j++) s.push_back(gi());
- store.push_back(s);
- }
- for(int i=0; i<r; i++) rent[i]=gi();
- sort(milk, milk+n);
- sort(store.begin(), store.end(), sortp);
- sort(rent, rent+r);
- for(int i=n-1; i>=0; i--)
- msuffix[i]=i==n-1?milk[i]:milk[i]+msuffix[i+1];
- for(int i=r-1; i>=0; i--)
- rsuffix[i]=i==r-1?rent[i]:rent[i]+rsuffix[i+1];
- ll ans=0;
- for(int i=0, j=1; i<n-1&&j<n; i++, j++) {
- ll ans1=0;
- int milkamt=msuffix[j];
- for(int k=m-1; k>=0; k--) {
- if(milkamt-store[k][0]>0) {
- milkamt-=store[k][0];
- ans1+=store[k][0]*store[k][1];
- } else {
- ans1+=store[k][1]*milkamt;
- break;
- }
- }
- ans1+=rsuffix[(r-1)-(i+1)+1];
- ans=max(ans1, ans);
- }
- printf("%d\n", ans);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement