Задача №115174. Выиграй МКОШП
Как вы все знаете, МКОШП — это Московская Командная Олимпиада Школьников по Пошаговым стратегиям. На новом этапе олимпиады произошло что-то странное: приглашена только одна команда, и ей предложен только один шаг.
Команда состоит из \(n\) школьников, им предстоит сражаться с \(m\) монстрами. Каждый школьник характеризуется тремя параметрами — \(i\)-й школьник имеет \(h_i\) здоровья, \(a_i\) атаки и \(b_i\) защиты. Каждый монстр также характеризуется тремя числами — \(j\)-й монстр имеет \(w_j\) здоровья, целью его атаки будет \(t_j\)-й школьник, и монстр нанесет ему \(d_j\) урона. Игра состоит всего из двух ходов: сначала ходят школьники, а потом монстры атакуют свои цели. Во время своего хода каждый школьник может сделать одно из двух действий:
- Выбрать любого монстра и атаковать его, тогда здоровье этого монстра уменьшится на \(a_i\) (то есть на силу атаки школьника).
- Повесить защиту на какого-то школьника, тогда здоровье этого школьника увеличится на \(b_i\). Обратите внимание, что школьник может повесить защиту сам на себя. Также если два школьника повесили защиту на одного и того же, то обе защиты будут складываться.
Если после хода школьников здоровье монстра станет меньше или равно 0, то он не сможет атаковать школьника, на которого нацелился. После хода школьников все монстры с положительным здоровьем атакуют школьников. После хода монстров игра заканчивается. Если здоровье школьника стало меньше или равно 0, то школьник как игрок выбывает из соревнования. Ваша задача сказать, какое максимальное количество школьников смогут остаться в игре.
В первой строке даны два числа \(n\) и \(m\) (\(1 \leqslant n \leqslant 12\), \(1 \leqslant m \leqslant 100\)) — количество школьников и количество монстров соответственно.
Следующие \(n\) строк содержат по три числа: \(h_i, a_i, b_i\) (\(1 \leqslant h_i, a_i, b_i \leqslant 10^9\)) — характеристики здоровья, атаки и защиты \(i\)-го школьника соответственно.
Следующие \(m\) строк содержат по три числа: \(w_j, t_j, d_j\) (\(1 \leqslant w_j, d_j \leqslant 10^9, 1 \leqslant t_j \leqslant n\)) — здоровье, цель и силу атаки \(j\)-го монстра соответственно.
Выведите одно число — максимальное количество школьников, которые могут остаться в игре.
2 3 1 2 3 3 1 2 3 1 1 3 1 2 1 1 9
2
3 4 1 2 3 1 2 3 1 2 3 1 1 1 1 1 3 1 2 1 5 2 5
2