У вас есть \(n\) интервалов \([l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]\) таких, что \(l_i < r_i\) для каждого \(i\), и все конечные точки интервалов различны.
Вес \(i\)-го интервала составляет \(c_i\) на единицу длины. Поэтому вес \(i\)-го интервала равен \(c_i \cdot (r_i - l_i)\).
Вам не нравятся большие веса, поэтому вы хотите сделать сумму весов всех интервалов как можно меньше. Оказывается, вы можете выполнять следующие три типа операций:
- переставить элементы массива \(l\) в любом порядке;
- переставить элементы массива \(r\) в любом порядке;
- переставить элементы массива \(c\) в любом порядке.
Однако после выполнения всех операций интервалы должны оставаться корректными (т.е. для каждого \(i\) должно выполняться условие \(l_i < r_i\)).
Какова минимально возможная сумма весов интервалов после выполнения этих операций?
Выходные данные
Для каждого набора входных данных выведите одно целое число: минимально возможную сумму всех весов интервалов после ваших операций.
Примечание
В первом наборе входных данных вы можете сделать так
- \(l = [8, 3]\);
- \(r = [23, 12]\);
- \(c = [100, 100]\).
В этом случае будет два интервала:
- интервал \([8, 23]\) с весом \(100\) на единицу длины, тогда вес интервала равняется \(100 \cdot (23-8) = 1500\);
- интервал \([3, 12]\) с весом \(100\) на единицу длины, тогда вес интервала равняется \(100 \cdot (12-3) = 900\);
Сумма весов составляет \(2400\). Можно показать, что не существует конфигурации конечных интервалов, сумма весов которых меньше \(2400\).
Во втором наборе входных данных можно сделать так
- \(l = [1, 2, 5, 20]\);
- \(r = [3, 4, 10, 30]\);
- \(c = [3, 3, 2, 2]\).
В этом случае будет четыре интервала:
- интервал \([1, 3]\) с весом \(3\) на единицу длины, вес всего интервала равен \(3 \cdot (3-1) = 6\);
- интервал \([2, 4]\) с весом \(3\) на единицу длины, вес всего интервала равен \(3 \cdot (4-2) = 6\);
- интервал \([5, 10]\) с весом \(2\) на единицу длины, вес всего интервала равен \(2 \cdot (10-5) = 10\);
- интервал \([20, 30]\) с весом \(2\) на единицу длины, вес всего интервала равен \(2 \cdot (30-20) = 20\).
Сумма весов равна \(42\). Можно показать, что не существует конфигурации конечных интервалов, сумма весов которых меньше \(42\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
2
8 3
12 23
100 100
4
20 1 2 5
30 4 3 10
2 3 2 3
|
2400
42
|