Тур состоит из \(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\) прибыли. Вычислите, какую максимальную прибыль вы можете получить при правильном выборе моделей и порядка их выступления, при условии соблюдения всех ограничений.
Выходные данные
Выведите одно целое число — максимальную суммарную прибыль.
Примечание
В первом примере в тур приглашены \(3\) модели. Шоу состоит из моделей в следующем порядке \([1, 3, 4]\).
Соответственные рейтинги в городах:
- Город \(1\) — \([ 1, 3, 4 ]\).
- Город \(2\) — \([ 1, 2, 3 ]\).
- Город \(3\) — \([ 2, 4, 5 ]\).
Видно, что рейтинги моделей в каждом городе возрастают. Суммарная прибыль равна \(10 + 10 + 10 = 30\). Можно доказать, что невозможно достичь большей прибыли.
Во втором примере мы можем пригласить в тур пятую модель, откуда получаем общую прибыль \(50\). Можно доказать, что невозможно достичь большей прибыли.
В третьем примере мы приглашаем в тур единственную модель, откуда получаем прибыль \(1\,000\,000\,000\).
В четвертом примере мы можем пригласить всех моделей и шоу будет состоять из моделей в следующем порядке \([ 5, 4, 3, 2, 1 ]\). Тогда общая прибыль будет равна \(5 \cdot 1\,000\,000\,000 = 5\,000\,000\,000\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
10 10 10 10 10
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1
|
30
|
|
2
|
3 5
10 10 10 10 50
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1
|
50
|
|
3
|
1 1
1000000000
1
|
1000000000
|
|
4
|
5 5
1000000000 1000000000 1000000000 1000000000 1000000000
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
|
5000000000
|
|
5
|
1 3
1 2 3
3 3 3
|
3
|