题目描述

一个时尚之旅包括在不同城市举行的多场在不同的城市举行相同的走秀。 有n个名模特愿意参加巡演，编号从1到n。

不同城市的人对时尚行业有不同的看法，所以他们对每个模特的评价也不同。 特别的是，城市i的人们对模特j的评分为ri,j。

你要选择k数量的模特，以及它们的顺序，让所选模型的指数为j1,j2,...,jk。 模特将按照这个顺序一个接一个地走在T台上。为了使表演精彩，在每个城市，模特的评分应该按照她们的表现顺序严格增加。 更正式地说，对于任何城市i和下标t (2≤t≤k)，评分必须满足ri,jt-1

毕竟，时尚行业是关于金钱的，所以选择模特j参加巡演，就能为你带来pj的钱。 计算在满足所有要求的情况下，你通过选择模特和她们的顺序所能获得的最大总利润。

输入格式

第一行包含两个整数m和n (1≤m≤500, 1≤n≤5000) --分别是节目的数量和愿意参加的模特的数量。

第二行包含n个整数pj (1≤pj≤1000000000) --你邀请第j个模特参加巡演的利润。

接下来的m行分别包含n整数。 第i行包含n个整数ri,j (1≤ri,j≤n) --城市i中模型的评级。

输出格式

输出一个整数 --你能得到的最大总金额。

3 5
10 10 10 10 10
1 2 3 4 5
1 5 2 3 4
2 3 4 5 1

30

提示

在第一个例子中，有3个被邀请的模特。该节目由模特组成，顺序为[1,3,4]

然后，各城市相应的评分如下： 城市1 - [1,3,4] 城市2 - [1,2,3] 城市3 - [2,4,5]

你可以看到评级在增加。所以总利润是10+10+10=30。 可以证明，我们不可能实现更大的利润。