Задача номер 10. Задача "RPG"

10. Задача "RPG"

В играх жанра RPG (role-playing game) игроки управляют персонажами, которые характеризуются несколькими атрибутами. В нашей простой игре у персонажа всего два атрибута: сила Str и ловкость Dex. Изначально персонаж наделен некоторыми способностями, поэтому его атрибуты имеют некоторое начальное значение. Игроки стремятся повысить атрибуты своих персонажей с помощью надевания на них вещей. Вещи могут повышать атрибуты на фиксированную величину или не изменять их. Например, можно надеть на персонажа шлем, который увеличит его силу, но никак не будет влиять на ловкость. Все вещи делятся на заданное количество типов: шлемы, доспехи, перчатки, сапоги и так далее. Причем на персонаже может быть надета максимум одна вещь каждого типа. Задача выбора набора надетых вещей осложняется тем, что вещи имеют требования к атрибутам персонажа. Если требуется надеть вещь определенного типа, то на персонаже не должно быть надето вещи данного типа, и значение каждого атрибута с учетом бонусов от остальных надетых на персонажа вещей не должно быть меньше, чем требование к этому атрибуту у заданной вещи.

Однажды вашему персонажу повезло, он нашел клад, в котором было большое количество вещей. Но унести вещи он сможет, только надев их на себя. Вам приглянулась одна вещь, которую вы хотите, во что бы то ни стало, унести с собой. Ваша задача определить, существует ли такой порядок надевания вещей, чтобы в итоге надеть ту самую вещь и уйти с трофеями.

До того как был найден клад, на персонаже не было ни одной вещи.

Входные данные

В первой строке входного файла записано два целых числа K и N — количество типов вещей и общее количество различных вещей (1 <= K <= 5, 1 <= N <= 3000).

Во второй строке описаны базовые значения атрибутов персонажа: целые числа Str и Dex (0 <= Str, Dex <= 100).

Далее идут N строк, каждая из которых описывает одну вещь. Описание каждой вещи содержит пять целых чисел: Typei, RStri, RDexi, AStri, ADexi — соответственно тип вещи, ее требования к атрибутам и ее бонусы к атрибутам (1 <= Typei <= K, 0 <= RStri, RDexi, AStri, ADexi <= 101).

Считается, что требуется надеть первую вещь.

Выходные данные

В единственную строку выходного файла необходимо вывести слово YES или слово NO. YES должно быть выведено, если указанную вещь можно надеть, NO — в противном случае.

Примеры

input.txt
1 1
10 20
1 0 10 10 10

output.txt
YES

input.txt
1 1
10 10
1 0 20 10 10

output.txt
NO

Соревнование: XI Открытая Всесибирская олимпиада по программированию имени И.В. Поттосина 2010
Источник: http://olimpic.nsu.ru