Рома играет в новое дополнение к его любимой игре — World of Darkraft. Рома только что закончил создавать персонажа и готов выйти на первую охоту на монстров.

Перед охотой Рома должен купить оружие и комплект брони. Он может выбрать ровно одно из $$$n$$$ различных типов оружия и ровно один из $$$m$$$ различных комплектов брони. Оружие $$$i$$$ имеет модификатор атаки $$$a_i$$$ и стоит $$$ca_i$$$ монет, комплект брони $$$j$$$ имеет модификатор защиты $$$b_j$$$ и стоит $$$cb_j$$$ монет.

После выбора экипировки Рома может начать охотиться на монстров. Всего есть $$$p$$$ монстров, которых можно попытаться победить. У каждого монстра $$$k$$$ есть три параметра: защита $$$x_k$$$, атака $$$y_k$$$ и награда за его убийство $$$z_k$$$. Рома может победить монстра только в том случае, если модификатор атаки его оружия больше, чем защита монстра, а модификатор защиты его брони больше, чем атака монстра. То есть монстра $$$k$$$ можно победить с использованием оружия $$$i$$$ и комплекта брони $$$j$$$, если $$$a_i > x_k$$$ и $$$b_j > y_k$$$. После победы над монстром Рома получает награду за него. Во время охоты можно попробовать победить любое количество монстров в любом порядке — но они не появляются заново после смерти, поэтому каждого монстра можно победить только один раз.

Благодаря внесенным в игру деньгам Рома может себе позволить любое оружие и любой комплект брони. Несмотря на это, ему все равно необходимо распланировать охоту так, чтобы получить максимальную прибыль. Прибыль с охоты считается как разность между количеством монет, полученных за убийство монстров, и ценой выбранного оружия и брони. Обратите внимание, что Рома должен купить оружие и броню, даже если охота не покроет расходы на них.

Помогите Роме максимизировать прибыль с охоты на монстров.