Тур состоит из $$$m$$$ идентичных подиумных шоу в разных городах. Всего есть $$$n$$$ моделей, которые хотят участвовать в туре, пронумерованных от $$$1$$$ до $$$n$$$. У людей в разных городах разные взгляды на индустрию моды, поэтому они оценивают моделей по-разному. В частности, люди в городе $$$i$$$ оценивают модель $$$j$$$ рейтингом $$$r_{i, j}$$$.

Из желающих моделей вы выберете $$$k$$$ моделей и некоторый их порядок, пусть эти модели в этом порядке имеют номера $$$j_1, j_2, \dots, j_k$$$. В каждом городе на подиум выйдут эти $$$k$$$ моделей в данном порядке. Чтобы сделать шоу захватывающим, в каждом городе рейтинги моделей должны строго возрастать в порядке их выхода на подиум. Более формально, для любого города $$$i$$$ и индекса $$$t$$$ ($$$2 \leq t \leq k$$$), рейтинги должны удовлетворять условию $$$r_{i,j_{t - 1}} < r_{i,j_t}$$$.

В конце концов, индустрия моды сфокусирована на деньгах, поэтому выбрав модель $$$j$$$ для участия в туре, вы получите $$$p_j$$$ прибыли. Вычислите, какую максимальную прибыль вы можете получить при правильном выборе моделей и порядка их выступления, при условии соблюдения всех ограничений.