Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на количество наборов входных данных и \(n\). В сложной версии количество наборов входных данных не превосходит \(10^4\), а сумма значений \(n\) по всем наборам входных данных не превосходит \(2 \cdot 10^5\). Кроме того, никаких дополнительных ограничений на значение \(n\) в одиночном наборе входных данных нет.
Недавно Алисе и Бобу родители подарили шарики \(n\) различных цветов: получилось, что у Алисы \(a_1\) шариков цвета \(1\), \(a_2\) шариков цвета \(2\),..., \(a_n\) шариков цвета \(n\). У Боба: \(b_1\) шариков цвета \(1\), \(b_2\) шариков цвета \(2\), ..., \(b_n\) шариков цвета \(n\). Все \(a_i\) и \(b_i\) от \(1\) до \(10^9\).
Посовещавшись, Алиса и Боб придумали следующую игру: игроки ходят по очереди, начиная с Алисы. На своём ходу игрок выбирает такой цвет \(i\), что у обоих игроков есть хотя бы по одному шарику этого цвета. Он выбрасывает один шарик цвета \(i\), а его противник — все шарики цвета \(i\). Игра заканчивается, когда не существует такого цвета \(i\), что у обоих игроков есть хотя бы по одному шарику этого цвета.
Счёт в игре — это количество оставшихся шариков у Алисы минус количество оставшихся шариков у Боба по окончании игры. То есть счёт равен \((A-B)\), где \(A\) — количество шариков у Алисы, а \(B\) — количество шариков у Боба в конце игры. Алиса хочет максимизировать счёт, а Боб — минимизировать.
Посчитайте, какой счёт будет в конце игры, если оба игрока играют оптимально.
Примечание
В первом примере один из способов получить счёт \(1\) — следующий:
- Алиса выбирает цвет \(1\), выбрасывает \(1\) шарик. Боб также выбрасывает \(1\) шарик;
- Боб выбирает цвет \(3\), выбрасывает \(1\) шарик. Алиса также выбрасывает \(1\) шарик;
- Алиса выбирает цвет \(2\), выбрасывает \(1\) шарик, а Боб — \(2\) шарика.
В результате у Алисы остается \(a = [3, 1, 0]\), а у Боба — \(b = [0, 0, 3]\). Счёт равен \(3 + 1 - 3 = 1\).
Можно показать, что ни Алиса ни Боб не могут получить лучший счёт, если оба играют оптимально.
Во втором примере Алиса может сначала выбрать цвет \(1\), далее Боб выберет цвет \(4\), после этого Алиса выберет цвет \(2\), и Боб — цвет \(3\). Можно показать, что это оптимальная игра.