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

Задача . B. Уравнивание подарков


Задача

Темы: жадные алгоритмы *800

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

За один ход вы можете выбрать некоторый подарок \(1 \le i \le n\) и совершить одно из следующих действий:

  • съесть ровно одну конфету из этого подарка (уменьшить \(a_i\) на один);
  • съесть ровно один апельсин из этого подарка (уменьшить \(b_i\) на один);
  • съесть ровно одну конфету и ровно один апельсин из этого подарка (уменьшить и \(a_i\), и \(b_i\) на один).

Разумеется, вы не можете съесть конфету или апельсин, если их нет в подарке (поэтому ни \(a_i\), ни \(b_i\) не могут стать меньше нуля).

Как было сказано выше, все подарки должны быть равны. Это означает, что после некоторой последовательности ходов должны быть выполнены следующие два условия: \(a_1 = a_2 = \dots = a_n\) и \(b_1 = b_2 = \dots = b_n\) (и равенство \(a_i\) и \(b_i\) не является необходимым).

Ваша задача — найти минимальное количество ходов, необходимое, чтобы уравнять все заданные подарки.

Вам необходимо ответить на \(t\) независимых наборов тестовых данных.

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

Первая строка теста содержит одно целое число \(t\) (\(1 \le t \le 1000\)) — количество наборов тестовых данных. Затем следуют \(t\) наборов тестовых данных.

Первая строка набора тестовых данных содержит одно целое число \(n\) (\(1 \le n \le 50\)) — количество подарков. Вторая строка набора тестовых данных содержит \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le 10^9\)), где \(a_i\) — количество конфет в \(i\)-м подарке. Третья строка набора тестовых данных содержит \(n\) целых чисел \(b_1, b_2, \dots, b_n\) (\(1 \le b_i \le 10^9\)), где \(b_i\) — количество апельсинов в \(i\)-м подарке.

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

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

Примечание

В первом наборе тестовых данных примера мы можем выполнить следующую последовательность ходов:

  • выбрать первый подарок и съесть один апельсин из него, таким образом \(a = [3, 5, 6]\) и \(b = [2, 2, 3]\);
  • выбрать второй подарок и съесть одну конфету из него, таким образом \(a = [3, 4, 6]\) и \(b = [2, 2, 3]\);
  • выбрать второй подарок и съесть одну конфету из него, таким образом \(a = [3, 3, 6]\) и \(b = [2, 2, 3]\);
  • выбрать третий подарок и съесть одну конфету и один апельсин из него, таким образом \(a = [3, 3, 5]\) и \(b = [2, 2, 2]\);
  • выбрать третий подарок и съесть одну конфету из него, таким образом \(a = [3, 3, 4]\) и \(b = [2, 2, 2]\);
  • выбрать третий подарок и съесть одну конфету из него, таким образом \(a = [3, 3, 3]\) и \(b = [2, 2, 2]\).

Примеры
№Входные данныеВыходные данные
1 5
3
3 5 6
3 2 3
5
1 2 3 4 5
5 4 3 2 1
3
1 1 1
2 2 2
6
1 1000000000 1000000000 1000000000 1000000000 1000000000
1 1 1 1 1 1
3
10 12 8
7 5 4 
6
16
0
4999999995
7

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

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

Ваш ответ

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


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

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