inline constexpr long START=1, TOWN=2, END=3;

struct Event {
    long position{0};
    long type{1};
    long population{0};
    size_t cloud_idx{0};
    Event(long p, long t, long popn, size_t idx=0) : position(p), type(t), population{popn}, cloud_idx{idx} {}
    bool operator<(const Event& other)
    {
        return std::tie(position, type) < std::tie(other.position, other.type);
    }
};

long maximumPeople(vector<long>& p,vector<long>& x, vector<long>& y, vector<long>& r) {
    // Return the maximum number of people that will be in a sunny town after removing exactly one cloud.
    std::vector<Event> all_events;
    std::transform(
        p.begin(), p.end(),
        x.begin(),
        std::back_inserter(all_events),
        [](long popn, long pos)
        {
            return Event(pos, TOWN, popn);
        }
    );
    std::inner_product(
        y.begin(), y.end(),
        r.begin(),
        std::reference_wrapper(all_events),
        [idx=0ll](auto&& v, const auto& pair) mutable {
            const auto& [pos, rad] = pair;
            v.get().emplace_back(pos-rad, START, -1, idx);
            v.get().emplace_back(pos+rad, END, -1, idx);
            ++idx;
            return std::move(v);
        },
        [](long pos, long rad)
        {
            return std::make_pair(
                pos, rad
            );
        }
    );
    // cout << all_events.size() << endl;
    std::sort(all_events.begin(), all_events.end());
    std::unordered_set<long> active_cloud;
    std::unordered_map<size_t, long> cloud_to_popn;
    long always_sunny = 0;
    for (const auto& event : all_events)
    {
        switch (event.type)
        {
            case START:
                active_cloud.emplace(event.cloud_idx);
                break;
            case TOWN:
                if (active_cloud.size() == 1)
                {
                    cloud_to_popn[*active_cloud.begin()] += event.population;
                }
                else if (active_cloud.size() == 0)
                {
                    always_sunny += event.population;
                }
                break;
            case END:
                active_cloud.erase(event.cloud_idx);
                break;
            default:
                break;
        }
    }
    auto max_elem = std::max_element(
        cloud_to_popn.begin(),
        cloud_to_popn.end(),
        [](const auto& p1, const auto& p2){ return p1.second < p2.second;}
    );
    long ret = always_sunny + (max_elem != cloud_to_popn.end() ? max_elem->second : 0ll);
    return ret;
}