#P17799. [Ontak2024]MAK

[Ontak2024]MAK

题目描述

给定两个长度为 NN 的正整数序列 X,YX,Y,以及 MM 个同样长的序列 A1,…,AMA_1,\ldots,A_M。

依次处理 i=1,…,Mi=1,\ldots,M。每次必须选择下面两种操作中的恰好一种:

  • 对所有 jj,令 X[j]←max⁡(X[j],Ai[j])X[j]\leftarrow\max(X[j],A_i[j]);
  • 对所有 jj,令 Y[j]←max⁡(Y[j],Ai[j])Y[j]\leftarrow\max(Y[j],A_i[j])。

一次操作对整个序列生效,不能把同一个 AiA_i 的不同坐标分配给不同序列。

求所有操作结束后

∑j=1N(X[j]+Y[j])\sum_{j=1}^{N}\bigl(X[j]+Y[j]\bigr)

的最大可能值。

输入格式

第一行两个整数 N,MN,M。

接下来两行分别包含 NN 个整数,描述初始的 X,YX,Y。

接下来 MM 行,每行 NN 个整数,依次描述 A1,…,AMA_1,\ldots,A_M。

输出格式

输出一个整数,表示目标式的最大值。

数据范围

1≤N≤121\le N\le12,1≤M≤1000001\le M\le100000。所有序列中的数均在 [1,10000000][1,10000000] 内。

样例 1

输入:

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

输出:

25

样例 2

输入:

3 3
1 1 2
1 2 1
2 1 2
1 1 1
1 1 2

输出:

10

样例 3

输入:

3 5
4 13 10
14 9 4
4 6 4
13 18 16
8 13 5
7 18 17
20 20 14

输出:

105

子任务

表中的 Ai[j]≤2A_i[j]\le2 仅限制 AA,不额外限制初始 X,YX,Y。

编号 附加限制 分值
1 N=1N=1 6
2 N≤8,M≤100N\le8,M\le100,所有 Ai[j]≤2A_i[j]\le2 15
3 M≤100M\le100,所有 Ai[j]≤2A_i[j]\le2 12
4 N≤7,M≤100N\le7,M\le100 9
5 N≤9,M≤100N\le9,M\le100
6 N≤7N\le7 8
7 N≤8N\le8 7
8 N≤9N\le9 6
9 N≤10N\le10 5
10 N≤11N\le11 4
11 无附加限制 19