Guest User

Untitled

a guest
Aug 18th, 2019
83
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define F first
  5. #define S second
  6. typedef pair<int, int> ii;
  7. typedef vector<int> vi;
  8. inline ll gi() {
  9. ll x=0,f=1;
  10. char ch=getchar();
  11. while(!isdigit(ch))f^=ch=='-',ch=getchar();
  12. while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
  13. return f?x:-x;
  14. }
  15. bool sortp(const vector<int> &a, const vector<int> &b) {
  16. return a[1]<b[1];
  17. }
  18. int milk[100005], msuffix[100005], rent[100005], rsuffix[100005];
  19. vector<vi> store;
  20. int main() {
  21. #ifndef HOME
  22. freopen("rental.in", "r", stdin);
  23. freopen("rental.out", "w", stdout);
  24. #endif
  25. int n=gi(), m=gi(), r=gi();
  26. for(int i=0; i<n; i++) milk[i]=gi();
  27. for(int i=0; i<m; i++) {
  28. vi s;
  29. for(int j=0; j<2; j++) s.push_back(gi());
  30. store.push_back(s);
  31. }
  32. for(int i=0; i<r; i++) rent[i]=gi();
  33. sort(milk, milk+n);
  34. sort(store.begin(), store.end(), sortp);
  35. sort(rent, rent+r);
  36. for(int i=n-1; i>=0; i--)
  37. msuffix[i]=i==n-1?milk[i]:milk[i]+msuffix[i+1];
  38. for(int i=r-1; i>=0; i--)
  39. rsuffix[i]=i==r-1?rent[i]:rent[i]+rsuffix[i+1];
  40. ll ans=0;
  41. for(int i=0, j=1; i<n-1&&j<n; i++, j++) {
  42. ll ans1=0;
  43. int milkamt=msuffix[j];
  44. for(int k=m-1; k>=0; k--) {
  45. if(milkamt-store[k][0]>0) {
  46. milkamt-=store[k][0];
  47. ans1+=store[k][0]*store[k][1];
  48. } else {
  49. ans1+=store[k][1]*milkamt;
  50. break;
  51. }
  52. }
  53. ans1+=rsuffix[(r-1)-(i+1)+1];
  54. ans=max(ans1, ans);
  55. }
  56. printf("%d\n", ans);
  57. return 0;
  58. }
RAW Paste Data