Олимпиадный тренинг

Задача . D. Три активности


Задача

Темы: дп жадные алгоритмы Перебор реализация сортировки *1200

Приближаются зимние каникулы. Они будут длиться \(n\) дней.

Во время каникул Монокарп с друзьями хочет ровно по одному разу:

  • пойти кататься на лыжах;
  • посмотреть фильм в кинотеатре;
  • поиграть в настольные игры.

Монокарп знает, что в \(i\)-й день ровно \(a_i\) друзей соберутся на катание на лыжах, \(b_i\) друзей — на просмотр фильма и \(c_i\) друзей — на настольные игры.

Монокарп также знает, что он не может заниматься более чем одной активностью в течение одного дня.

Поэтому он просит вас помочь ему выбрать три различных дня \(x, y, z\) таким образом, чтобы общее количество друзей, присоединившихся к нему на активности (\(a_x + b_y + c_z\)), было максимальным.

Входные данные

Первая строка содержит одно целое число \(t\) (\(1 \le t \le 10^4\)) — количество наборов входных данных.

Первая строка каждого теста содержит одно целое число \(n\) (\(3 \le n \le 10^5\)) — продолжительность зимних каникул в днях.

Вторая строка содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^8\)) — количество друзей, которые присоединятся к Монокарпу для катания на лыжах в \(i\)-й день.

Третья строка содержит \(n\) целых чисел \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^8\)) — количество друзей, которые присоединятся к Монокарпу для просмотра фильма в \(i\)-й день.

Четвертая строка содержит \(n\) целых чисел \(c_1, c_2, \dots, c_n\) (\(1 \le c_i \le 10^8\)) — количество друзей, которые присоединятся к Монокарпу для настольных игры в \(i\)-й день.

Сумма \(n\) по всем тестам не превышает \(10^5\).

Выходные данные

На каждый набор входных данных выведите одно целое число — максимальное суммарное количество друзей, которые могут присоединиться к Монокарпу за три различных дня.

Примечание

В первом наборе входных данных Монокарп может выбрать день \(2\) для катания на лыжах, день \(1\) для просмотра фильма и день \(3\) для настольных игр. Таким образом, \(a_2 = 10\) друзей присоединятся к нему для катания на лыжах, \(b_1 = 10\) друзей присоединятся к нему для просмотра фильма и \(c_3 = 10\) друзей присоединятся к нему для настольных игр. Общее количество друзей составляет \(30\).

Во втором наборе Монокарп может выбрать день \(1\) для катания на лыжах, день \(4\) для просмотра фильма и день \(2\) для настольных игр. Всего соберется \(30 + 20 + 25 = 75\) друзей. Обратите внимание, что Монокарп не может выбрать день \(1\) для всех активностей, потому что он не может заниматься более чем одной активностью в течение одного дня.

В третьем наборе Монокарп может выбрать день \(2\) для катания на лыжах, день \(3\) для просмотра фильма и день \(7\) для настольных игр. Всего соберется \(19 + 19 + 17 = 55\) друзей.

В третьем наборе Монокарп может выбрать день \(1\) для катания на лыжах, день \(4\) для просмотра фильма и день \(9\) для настольных игр. Всего соберется \(17 + 19 + 20 = 56\) друзей.


Примеры
№Входные данныеВыходные данные
1 4
3
1 10 1
10 1 1
1 1 10
4
30 20 10 1
30 5 15 20
30 25 10 10
10
5 19 12 3 18 18 6 17 10 13
15 17 19 11 16 3 11 17 17 17
1 17 18 10 15 8 17 3 13 12
10
17 5 4 18 12 4 11 2 16 16
8 4 14 19 3 12 6 7 5 16
3 4 8 11 10 8 10 2 20 3 
30
75
55
56

time 2000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w643
Комментарий учителя

Ваш ответ

выберите язык и введите исходный код


Для отправки решения задачи необходимо зарегистрироваться или авторизоваться!
     

Загруженные файлы
Нет