题目描述
给定两个长度为 N 的正整数序列 X,Y,以及 M 个同样长的序列 A1,…,AM。
依次处理 i=1,…,M。每次必须选择下面两种操作中的恰好一种:
- 对所有 j,令 X[j]←max(X[j],Ai[j]);
- 对所有 j,令 Y[j]←max(Y[j],Ai[j])。
一次操作对整个序列生效,不能把同一个 Ai 的不同坐标分配给不同序列。
求所有操作结束后
j=1∑N(X[j]+Y[j])
的最大可能值。
输入格式
第一行两个整数 N,M。
接下来两行分别包含 N 个整数,描述初始的 X,Y。
接下来 M 行,每行 N 个整数,依次描述 A1,…,AM。
输出格式
输出一个整数,表示目标式的最大值。
数据范围
1≤N≤12,1≤M≤100000。所有序列中的数均在 [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]≤2 仅限制 A,不额外限制初始 X,Y。
| 编号 |
附加限制 |
分值 |
| 1 |
N=1 |
6 |
| 2 |
N≤8,M≤100,所有 Ai[j]≤2 |
15 |
| 3 |
M≤100,所有 Ai[j]≤2 |
12 |
| 4 |
N≤7,M≤100 |
9 |
| 5 |
N≤9,M≤100 |
| 6 |
N≤7 |
8 |
| 7 |
N≤8 |
7 |
| 8 |
N≤9 |
6 |
| 9 |
N≤10 |
5 |
| 10 |
N≤11 |
4 |
| 11 |
无附加限制 |
19 |