#include "bits/stdc++.h" template requires std::default_initializable && requires { Dimension != 0; } class imos : protected std::conditional_t< Dimension == 1, std::vector, std::vector> > { friend imos; private: using lower_dimension = std::conditional_t< Dimension == 1, T, imos >; imos &operator+=(const imos &ci) { for (std::size_t i = 0; i < this->size(); ++i) { (*this)[i] += ci[i]; } return *this; } public: explicit imos(const std::size_t size, const auto... sizes) requires requires { 1 + sizeof...(sizes) == Dimension; } : std::vector( size + 1, lower_dimension(sizes...) ) { } const T& at(const std::size_t index, const auto... indices) const requires requires { 1 + sizeof...(indices) == Dimension; } { if constexpr (sizeof...(indices) == 0) { return (*this)[index]; } else { return (*this)[index].at(indices...); } } void set( const std::span begin, const std::span end, const T weight ) { const std::size_t begin0 = std::min(begin.front(), this->size() - 1); const std::size_t end0 = std::min(end.front(), this->size() - 1); if constexpr (Dimension > 1) { (*this)[begin0].set( begin.template last(), end.template last(), weight ); (*this)[end0].set( begin.template last(), end.template last(), -weight ); } else { (*this)[begin0] += weight; (*this)[end0] -= weight; } } void set( const std::array &begin, const std::array &end, const T weight ) { set(std::span{begin}, std::span{end}, weight); } void accumulate() { for (std::size_t i = 1; i < this->size(); ++i) { (*this)[i] += (*this)[i - 1]; } if constexpr (Dimension > 1) { for (auto &child : *this) { child.accumulate(); } } } }; template class cyclic_imos final : public imos { public: using imos::imos; void set_cyclic( const std::span begin, const std::span end, const T weight ) { this->set(begin, end, weight); if constexpr (Dimension > 1) { for (unsigned i = 1; i < (1 << Dimension); ++i) { std::array correction_begin, correction_end; for (unsigned j = 0; j < Dimension; ++j) { if (i & (1 << j)) { if (begin[j] <= end[j]) { goto CONTINUE; } correction_begin[j] = 0; correction_end[j] = this->size() - 1; } else { correction_begin[j] = begin[j]; correction_end[j] = end[j]; } } this->set(correction_begin, correction_end, weight); CONTINUE: ; } } else { if (begin.front() > end.front()) { (*this).front() += weight; (*this).back() -= weight; } } } void set_cyclic( const std::array &begin, const std::array &end, const T weight ) { set_cyclic(std::span{begin}, std::span{end}, weight); } }; template auto make_imos(auto... sizes) { return imos(sizes...); } template auto make_cyclic_imos(auto... sizes) { return cyclic_imos(sizes...); } int main() { struct enemy { int x, y, hp; }; int n, k; std::cin >> n >> k; std::vector enemies(n); for (int i = 0; i < n; ++i) { int x, y, hp; std::cin >> x >> y >> hp; enemies[i] = { x + 500, y + 500, hp }; } auto imos = make_imos(1001, 1001); for (int i = 0; i < k; ++i) { int x, y, w, h, d; std::cin >> x >> y >> w >> h >> d; x += 500; y += 500; imos.set( {y, x}, {y + h + 1, x + w + 1}, d ); } imos.accumulate(); std::cout << std::accumulate( enemies.begin(), enemies.end(), 0, [imos](int acc, const enemy &e) { return acc + std::max(0, e.hp - imos.at(e.y, e.x)); } ) << std::endl; }