308103: CF1467C. Three Bags

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Three Bags

题意翻译

这道题的意思其实就是,给你三个背包: 每一次任选两个背包,在这两个背包中分别取出$a,b$这两个数(不放回),同时用$a-b$来替换$a$,那么经过数次操作以后,这三个背包中就只剩下一个数字了,请问这个数字的最大值。 输入格式是:第一行分别代表了这三个背包的背包容量,之后的三行分别代表的是这三个背包的全部数字。

题目描述

You are given three bags. Each bag contains a non-empty multiset of numbers. You can perform a number of operations on these bags. In one operation, you can choose any two non-empty bags, and choose one number from each of the bags. Let's say that you choose number $ a $ from the first bag and number $ b $ from the second bag. Then, you remove $ b $ from the second bag and replace $ a $ with $ a-b $ in the first bag. Note that if there are multiple occurrences of these numbers, then you shall only remove/replace exactly one occurrence. You have to perform these operations in such a way that you have exactly one number remaining in exactly one of the bags (the other two bags being empty). It can be shown that you can always apply these operations to receive such a configuration in the end. Among all these configurations, find the one which has the maximum number left in the end.

输入输出格式

输入格式


The first line of the input contains three space-separated integers $ n_1 $ , $ n_2 $ and $ n_3 $ ( $ 1 \le n_1, n_2, n_3 \le 3\cdot10^5 $ , $ 1 \le n_1+n_2+n_3 \le 3\cdot10^5 $ ) — the number of numbers in the three bags. The $ i $ -th of the next three lines contain $ n_i $ space-separated integers $ a_{{i,1}} $ , $ a_{{i,2}} $ , ..., $ a_{{i,{{n_i}}}} $ ( $ 1 \le a_{{i,j}} \le 10^9 $ ) — the numbers in the $ i $ -th bag.

输出格式


Print a single integer — the maximum number which you can achieve in the end.

输入输出样例

输入样例 #1

2 4 1
1 2
6 3 4 5
5

输出样例 #1

20

输入样例 #2

3 2 2
7 5 4
2 9
7 1

输出样例 #2

29

说明

In the first example input, let us perform the following operations: $ [1, 2], [6, 3, 4, 5], [5] $ $ [-5, 2], [3, 4, 5], [5] $ (Applying an operation to $ (1, 6) $ ) $ [-10, 2], [3, 4], [5] $ (Applying an operation to $ (-5, 5) $ ) $ [2], [3, 4], [15] $ (Applying an operation to $ (5, -10) $ ) $ [-1], [4], [15] $ (Applying an operation to $ (2, 3) $ ) $ [-5], [], [15] $ (Applying an operation to $ (-1, 4) $ ) $ [], [], [20] $ (Applying an operation to $ (15, -5) $ ) You can verify that you cannot achieve a bigger number. Hence, the answer is $ 20 $ .

Input

题意翻译

这道题的意思其实就是,给你三个背包: 每一次任选两个背包,在这两个背包中分别取出$a,b$这两个数(不放回),同时用$a-b$来替换$a$,那么经过数次操作以后,这三个背包中就只剩下一个数字了,请问这个数字的最大值。 输入格式是:第一行分别代表了这三个背包的背包容量,之后的三行分别代表的是这三个背包的全部数字。

加入题单

上一题 下一题 算法标签: