Задача №113790. Городская олимпиада
Завтра в столице Лайнландии пройдет городская олимпиада по программированию среди школьников.
Дома в столице расположены в целочисленных точках вдоль главной улицы. Для олимпиады будет организовано три места проведения, также расположенных на главной улице. Во всех трёх местах есть ограничение на максимальное количество участников, которые могут написать олимпиаду в этом месте.
Первое место проведения находится в точке с координатой a и вмещает максимум n a участников, второе находится в точке с координатой b и вмещает n b участников, а третье находится в точке с координатой c и вмещает n c участников.
В олимпиаде примет участие n школьников, i -й школьник живет в доме, который находится в точке с координатой x i . Для каждого школьника требуется выбрать место проведения, при этом запрещается превышать максимальное количество участников в каждом месте проведения. Гарантируется, что суммарная вместительность мест проведения достаточна, чтобы разместить всех школьников.
Если школьник живет в точке с координатой p , а место проведения олимпиады, куда он должен попасть, находится в точке с координатой q , то ему придется пройти расстояние | p - q | перед олимпиадой. Помогите организаторам найти минимальное суммарное расстояние, которое придётся пройти всем школьникам при их оптимальном распределении по местам проведения.
В первой строке находятся два целых числа a и n a — координата первого места проведения и его вместительность, во второй строке находятся два целых числа b и n b — координата второго места проведения и его вместительность, в третьей строке находятся два целых числа c и n c — координата третьего места проведения и его вместительность ( - 10 9 ≤ a , b , c ≤ 10 9 ; 1 ≤ n a , n b , n c ≤ 100 000 ).
В четвертой строке находится целое число n — количество школьников, которые примут участие в олимпиаде ( 1 ≤ n ≤ 100 000 , n ≤ n a + n b + n c ).
В следующей строке находятся n целых чисел x i — координаты домов, где живут участники олимпиады ( - 10 9 ≤ x i ≤ 10 9 ).
Выведите одно целое число — минимальное суммарное расстояние, которое придётся пройти школьникам до мест проведения.
0 1 3 2 6 3 4 -2 1 3 2
8