#include"monkey.h"
#include<bits/stdc++.h>
#define reg register
#define int long long
inline bool cmax(reg int &x,reg int y){return x<y?x=y,1:0;}
const int N=5e5+10;
int n,m;
std::vector<int> pl[N],pr[N];
std::map<std::pair<int,int>,int> f;
#undef int 
long long max_bananas(std::vector<int> A,std::vector<int> B,std::vector<std::pair<int,int>> P){
	#define int long long
    n=A.size(),m=B.size();
    for (auto [x,y]:P) pl[x].push_back(y),pr[y].push_back(x);
    for (reg int i=1;i<=n;i++) std::sort(pl[i].begin(),pl[i].end());
    for (reg int i=1;i<=m;i++) std::sort(pr[i].begin(),pr[i].end());
    for (reg int i=1;i<=n;i++){
        reg int lst=0;
        for (auto it:pl[i]){
            cmax(f[{i,it}],(lst?f[{i,lst}]:A[i-1])+B[it-1]);
            reg int pos=std::upper_bound(pr[it].begin(),pr[it].end(),i)-pr[it].begin();
            if (pos<pr[it].size()) pos=pr[it][pos],cmax(f[{pos,it}],f[{i,it}]+A[pos-1]);
            lst=it;
        }
    }
    reg int ans=0;
    for (auto [x,y]:f) cmax(ans,y); return ans;
}