#include <iostream> #include <algorithm> #include <set> using namespace std; #define X first #define Y second #define INF 0x7f7f7f7f int arr[10005], dp[10005]; pair<int, int> box[10005]; multiset<int> ms; int main() { ios::sync_with_stdio(0); cin.tie(0); int m, n; cin >> m >> n; for(int i = 0; i < m; i++) cin >> arr[i]; for(int i = 0; i < n; i++) cin >> box[i].X >> box[i].Y; sort(arr, arr+m, greater<>()); fill(dp+1, dp+m+1, INF); for(int i = 0; i < n; i++) { ms.clear(); for(int j = 0; j <= box[i].X; j++) if(m-j >= 0) ms.insert(dp[m-j]); for(int j = m; j >= 0; j--) { int temp = dp[j]; dp[j] = min(dp[j], *ms.begin() + box[i].Y); ms.erase(ms.find(temp)); if(j-box[i].X-1 >= 0) ms.insert(dp[j-box[i].X-1]); } } int ans = 0, sum = 0; for(int i = 0; i < m; i++) { sum += arr[i]; ans = max(ans, sum-dp[i+1]); } cout << ans << '\n'; }