Вам заданы два списка отрезков \([al_1, ar_1], [al_2, ar_2], \dots, [al_n, ar_n]\) и \([bl_1, br_1], [bl_2, br_2], \dots, [bl_n, br_n]\).
Первоначально, все отрезки \([al_i, ar_i]\) равны \([l_1, r_1]\) и все отрезки \([bl_i, br_i]\) равны \([l_2, r_2]\).
За один шаг вы можете выбрать один отрезок (либо из первого списка, либо из второго) и удлинить его на \(1\). Другими словами, предположим, вы выбрали отрезок \([x, y]\), тогда вы можете его превратить либо в \([x - 1, y]\), либо в \([x, y + 1]\).
Объявим суммарное пересечение \(I\) как сумму длин пересечений соответствующих пар отрезков, то есть \(\sum\limits_{i=1}^{n}{\text{intersection_length}([al_i, ar_i], [bl_i, br_i])}\). Пустое пересечение имеет длину \(0\), а длина отрезка \([x, y]\) равна \(y - x\).
Какое минимальное количество шагов необходимо выполнить, чтобы сделать \(I\) большим или равным \(k\)?
Примечание
В первом наборе входных данных, мы можем достигнуть суммарного пересечения \(5\), используя, например, следующую стратегию:
- превратим \([al_1, ar_1]\) из \([1, 2]\) в \([1, 4]\) за \(2\) шага;
- превратим \([al_2, ar_2]\) из \([1, 2]\) в \([1, 3]\) за \(1\) шаг;
- превратим \([bl_1, br_1]\) из \([3, 4]\) в \([1, 4]\) за \(2\) шага;
- превратим \([bl_2, br_2]\) из \([3, 4]\) в \([1, 4]\) за \(2\) шага.
В результате,
\(I = \text{intersection_length}([al_1, ar_1], [bl_1, br_1]) + \text{intersection_length}([al_2, ar_2], [bl_2, br_2]) + \\ + \text{intersection_length}([al_3, ar_3], [bl_3, br_3]) = 3 + 2 + 0 = 5\).
Во втором наборе, мы можем сделать \([al_1, ar_1] = [0, 1000000000]\) за \(1000000000\) шагов и \([bl_1, br_1] = [0, 1000000000]\) за \(1000000000\) шагов.
В третьем наборе, суммарное пересечение \(I\) уже равно \(10 > 3\), а потому, не нужно делать ни одного шага.