[ARC176] E - Max Vector

E - Max Vector

Time Limit: 2 sec / Memory Limit: 1024 MB

分数：800分

题面

给定两个长度为的正整数序列： 和 。

此外，给定个长度为的正整数序列。第个序列为。

对于每个，您必须执行以下操作之一。您可以独立选择对每个执行哪种操作。

• 将所有满足的整数，将替换为。
• 将所有满足的整数，将替换为。

找到在所有操作后的最小可能值。

限制条件

---

输入

输入以以下格式从标准输入给出：

输出

输出答案。

---

输入样例1

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

输出样例1

21

一种最优操作序列如下：

• 将替换为，使得。
• 将替换为，使得。

该操作序列可以获得。

---

输入样例2

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

输出样例2

84

---

输入样例3

5 12
330 68 248 387 491
295 366 376 262 192
280 121 17 168 455
288 179 210 378 490
150 275 165 264 287
66 331 207 282 367
303 215 456 214 18
227 326 103 443 427
395 57 107 350 227
318 231 146 2 116
57 325 124 383 260
147 319 23 177 445
254 198 32 85 56
68 177 356 41 471

输出样例3

3595