#include "bits/stdc++.h" template class imos : protected std::conditional_t< Dimension == 1, std::vector, std::vector> > { static_assert(Dimension != 0, "Dimension must not be 0."); friend imos; private: using lower_dimension = std::conditional_t< Dimension == 1, T, imos >; imos &operator+=(const imos &ci) { for (auto i = 0uz; i < this->size(); ++i) { (*this)[i] += ci[i]; } return *this; } public: explicit imos(const std::size_t size, const auto... sizes) : std::vector( size + 1, lower_dimension(sizes...) ) { static_assert( 1 + sizeof...(sizes) == Dimension, "Number of sizes must be equal to Dimension." ); if (size == 0) { throw std::invalid_argument("Each size of dimension must not be 0."); } } const T& at(const std::size_t index, const auto... indices) const { static_assert( 1 + sizeof...(indices) == Dimension, "Number of indices must be equal to 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 auto begin0 = std::min(begin.front(), this->size() - 1); const auto 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 set(std::size_t begin, std::size_t end, const T weight) { static_assert( Dimension == 1, "set(size_t, size_t, T) can be called only when Dimension == 1." ); return set(std::array{begin}, std::array{end}, weight); } void accumulate() { for (auto i = 0uz; i < this->size() - 1; ++i) { (*this)[i + 1] += (*this)[i]; } 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 (auto j = 0uz; 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); } void set_cyclic(std::size_t begin, std::size_t end, const T weight) { static_assert( Dimension == 1, "set_cyclic(size_t, size_t, T) can be called only when Dimension == 1." ); return set_cyclic(std::array{begin}, std::array{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; }