Задача №113340. Школьная демократия
В школе номер 932 проходят выборы в школьный совет. Выборы проходят по следующей системе. Завуч рассматривает список всех классов школы и разбивает их на группы. Каждая группа состав- лена из одного или нескольких классов, которые идут подряд в списке, каждый класс в результате разбиения попадает ровно в одну группу.
Каждая группа классов выдвигает двух кандидатов в школьный совет — одного мальчика и одну девочку. Далее каждый школьник голосует за одного из двух кандидатов своей группы. При этом известно, что мальчики всегда голосуют за кандидата-мальчика, а девочки — за кандидата- девочку. В каждой группе результаты голосования подводятся независимо. Кандидат, набравший наибольшее количество голосов в своей группе, считается избранным в школьный совет. В случае равенства голосов оба кандидата, выдвинутых в этой группе, считаются избранными в школьный совет.
Пусть в результате выборов в школьный совет пройдет B мальчиков и G девочек. По опыту прошлых лет завуч думает, что совет будет работать тем эффективней, чем больше разность \(B − G\) числа мальчиков и числа девочек в совете. Обратите внимание, что эта величина может оказаться и отрицательной, завуч хочет максимизировать именно само значение этой величины, а не ее модуль. Например, из вариантов \(B = 2, G = 5\), при котором \(B − G = −3\), и \(B = 3, G = 4\), при котором \(B − G = −1\), второй вариант предпочтительнее.
Всего в школе \(n\) классов, и завуч уже подготовил их список. Теперь ему предстоит разбить их на группы. Группа не может содержать меньше чем \(l\) классов, иначе совет будет очень большим. В то же время группа не может содержать больше чем \(r\) классов, иначе учащиеся не смогут договориться о выдвигаемых кандидатах. Напомним, что каждая группа должна быть составлена из классов, которые идут подряд в списке завуча.
Помогите завучу найти оптимальное по его мнению разбиение на группы.
В первой строке входного файла содержится два целых числа \(n, l\) и \(r (1 \le n \le 10^5, 1 \le l \le r \le n)\) — количество классов в школе, максимальное и минимальное допустимое количество классов в одной группе соответственно. В следующих \(n\) строках содержится по два целых числа \(b_i\) и \(g_i (1 \le b_i , g_i \le 10^4)\) — количество мальчиков и девочек в \(i\)-м классе, соответственно.
В первой строке выведите целое число \(x\) — количество групп в оптимальном по мнению завуча разбиении. В следующих \(x\) строках выведите по два числа \(s_i\) и \(f_i\) (\(1 \le s_i \le f_i \le n\)). Это означает, что в \(i\)-ю группу следует включить классы с \(s_i\)-го по \(f_i\)-й, включительно. Группы можно выводить в любом порядке. Каждый класс должен войти ровно в одну группу.
Гарантируется, что существует хотя бы одно разбиение, удовлетворяющее всем ограничениям. Если существует несколько оптимальных ответов, выведите любой.
5 1 2 7 5 10 1 2 3 2 6 4 3
4 1 1 2 3 4 4 5 5