#include using namespace std; struct Passenger { long long pickup; long long drop; long long value; }; long long taxiDriver(vector pickup, vector drop, vector tip){ int n = pickup.size(); if(n == 0) return 0; vector passengers(n); for(int i = 0; i < n; i++) { passengers[i] = Passenger{pickup[i], drop[i], drop[i] - pickup[i] + static_cast(tip[i])}; } sort(passengers.begin(), passengers.end(), [&](const Passenger &a, const Passenger &b) -> bool{ if(a.drop != b.drop) return a.drop < b.drop; return a.pickup < b.pickup; }); vector dp(n + 1, 0); for(int i = 1; i <= n; i++){ int j = -1; int low = 0, high = i - 2; while(low <= high){ int mid = low + (high - low) / 2; if(passengers[mid].drop <= passengers[i-1].pickup){ j = mid; low = mid + 1; } else high = mid - 1; } dp[i] = max(dp[i-1], (j != -1 ? dp[j+1] : 0) + passengers[i-1].value); } return dp[n]; } int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector pickup(n); for(auto &x: pickup) cin >> x; vector drop(n); for(auto &x: drop) cin >> x; vector tip(n); for(auto &x: tip) cin >> x; cout << taxiDriver(pickup, drop, tip); }