分赠花束

装备选完了，但CC坚持要带一束花——用矿区晶体拼成的花束，送给Echo。

"花束？"CC问。

"对。"你说，"$n$朵花，$m$个花瓶。花有高度，花瓶有高度。花只能放进不低于它高度的花瓶。"

"每个花瓶一朵？"

"对。"你说，"求最多能放多少朵花，且总美学值最大。"

"美学值？"

"对。"你说，"每朵花放进每个花瓶，有不同的美学值。"

"咋算？"

"动态规划。"你说，"$dp[i][j]$表示前$i$朵花放进前$j$个花瓶的最大美学值。"

"转移？"

"第$i$朵花放或不放第$j$个花瓶。"你说，"$dp[i][j]=\max(dp[i][j-1],dp[i-1][j-1]+value[i][j])$。"

"第47朵花。"你说，"高度47，只能放进高度$\ge 47$的花瓶。"

"花瓶够吗？"

"看有多少个高度$\ge 47$的。"你说，"如果够，就能放。"

"美学值呢？"

"看具体值。"你说，"不是高度匹配就好看，还要看搭配。"

"搭配？"

"对。"你说，"有些花单独好看，但放一起就不行。"

"像人。"CC说，"有些人单独好，放一起就吵。"

Echo看着那束晶体花——在数学空间的冷光下，折射出彩虹般的颜色。

"好看。"她说。

"送你。"CC说。

"送我？"

"对。"CC说，"你教了我们这么多，送你花。"

"我是投影。"Echo说，"拿不住花。"

"那放着。"CC说，"放着看。"

"好。"Echo说，"放着看。"

题目描述

$n$朵花，$m$个花瓶。花有高度$h_i$，花瓶有高度$H_j$。花$i$放进花瓶$j$有美学值$a_{ij}$。求最多放多少朵花，且总美学值最大。

输入格式

第一行$n$和$m$。接下来$n$行每行$m$个整数表示美学值。

输出格式

最多放的花数和最大美学值。

输入样例

5 10
3 1 12 3 15

输出样例

240

提示

• 先按高度排序花和花瓶。
• DP：$dp[i][j]$表示前$i$朵花前$j$个花瓶的最大价值。
• 时间复杂度$O(nm)$。