CF1826E Walk the Runway

一场时尚巡回演出包含 $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$ 的利润。请计算，在满足所有要求的前提下，你能获得的最大总利润。

第一行包含两个整数 $m$ 和 $n$（$1 \leq m \leq 500$，$1 \leq n \leq 5000$），分别表示演出的场数和愿意参加的模特人数。 第二行包含 $n$ 个整数 $p_j$（$1 \leq p_j \leq 10^9$），表示邀请第 $j$ 位模特参加巡回演出可以获得的利润。 接下来的 $m$ 行，每行包含 $n$ 个整数。第 $i$ 行的第 $j$ 个数 $r_{i, j}$（$1 \leq r_{i, j} \leq n$）表示第 $i$ 个城市对第 $j$ 位模特的评分。

输出一个整数，表示你能获得的最大总利润。

在第一个样例中，邀请了 $3$ 位模特，出场顺序为 $[1, 3, 4]$。 对应城市中的评分如下： - 城市 $1$ — $[1, 3, 4]$。 - 城市 $2$ — $[1, 2, 3]$。 - 城市 $3$ — $[2, 4, 5]$。 可以看到评分是递增的。因此总利润为 $10 + 10 + 10 = 30$。可以证明无法获得更高的利润。 在第二个样例中，可以只邀请第 $5$ 位模特参加巡回演出，总利润为 $50$。可以证明无法获得更高的利润。 在第三个样例中，只邀请唯一的模特参加巡回演出，总利润为 $1\,000\,000\,000$。 在第四个测试用例中，可以邀请所有模特，出场顺序为 $[5, 4, 3, 2, 1]$，总利润为 $5 \cdot 1\,000\,000\,000 = 5\,000\,000\,000$。 由 ChatGPT 4.1 翻译