eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Ассистенты

Ассистенты

Лимит времени 10 секунд
Лимит использования памяти 512 MiB

Профессор Байтазар возглавляет крупный научный проект. До завершения проекта ему осталось провести n независимых экспериментов (пронумерованных целыми числами от 1 до n).

Каждый эксперимент профессор может провести самостоятельно или перепоручить ассистенту. Если Байтазар решает провести i-й эксперимент самостоятельно, он должен затратить p_i подряд идущих дней на него. При этом он не может заниматься другими делами. Если Байтазар перепоручит эксперимент ассистенту, то он должен потратить один день на подбор ассистента (так как Байтазар привык всё делать основательно, то в этот день он не может отвлекаться на другие дела). Найденный ассистент начинает работу на следующий день и проведёт эксперимент в течение a_i подряд идущих дней. При этом профессор может заниматься какими-то другими делами. Считается, что Байтазар всегда может подобрать квалифицированного ассистента, который ещё не задействован в проекте.

Профессор попросил Вас составить расписание его действий так, чтобы завершить проект как можно раньше.

Входные данные

Первая строка ввода содержит целое число n (1n500000) - количество экспериментов, оставшихся Байтазару до завершения проекта.

Далее следует n строк, i-я из них содержит два целых числа p_i и a_i (1p_ia_i10^9), обозначающие количество дней, которые требуются для i-го эксперимента профессору и ассистенту соответственно.

Выходные данные

В первой строке выведите одно целое число k - минимальное количество дней, которое потребуется для завершения проекта. В последующих n строках выведите расписание экспериментов, позволяющее завершить проект за k дней.

Далее должны следовать n строк, i-я из них должна содержать график i-го эксперимента: сначала идёт буква "B" в случае, если профессор проводит i-й эксперимент самостоятельно, или "A" в случае, если он перепоручает эксперимент ассистенту, а затем через пробел идёт число t_i (1t_ik) - день, в который профессор начнёт работу над экспериментом (тогда эксперимент завершится в день t_i+p_i-1), или в который он будет искать нужного ассистента (который будет работать с (t_i+1)-го дня по (t_i+a_i)-й).

В случае, если оптимальных расписаний несколько, выведите любое.

Пример

Входные данные #1
5
2 6
2 6
2 5
2 2
1 2
Выходные данные #1
7
A 1
B 5
A 2
A 3
A 4
Источник Yandex.Algorithm, Online Round 1, July 14, 2013