ИОИП: Заключительный этап ИОИП 2018

Боузер — злодей, который часто похищает принцесс, и даже имеет для их заточения целое подземелье.

В подземелье расположено n тюремных камер. Камеры пронумерованы натуральными числами от 1 до n и расположены в этом порядке вдоль длинного коридора на одинаковом расстоянии друг от друга. Камера с номером i рассчитана на заточение a _i принцесс. Вход в подземелье расположен между камерами k и k + 1 , при этом, если k = 0 , это означает, что вход находится перед первой камерой. Если k = n , вход расположен после последней камеры.

Боузер собирается сделать m вылазок с целью похищения принцесс. В j -ю вылазку он планирует похитить b _j принцесс. Приведя их в подземелье, Боузер выбирает камеру для новых принцесс по следующему принципу:

• Если есть свободная камера с вместимостью a _i = b _j , то он обязательно выбирает такую камеру. Иначе он выбирает свободную камеру с вместимостью a _i > b _j .
• Из подходящих камер он выбирает ту, которая расположена как можно ближе ко входу. Если камер с одинаковым расстоянием до входа несколько, он выбирает ту, у которой номер меньше. Расстояние от входа до камеры Боузер считает равным количеству камер между ними.
• Если свободной камеры, подходящей по вместимости, нет, то ему остается лишь расстроиться и отпустить принцесс.

Чтобы не допустить побега принцесс, после того как Боузер заточил их в камеру, он закрывает камеру на ключ и выбрасывает его. Таким образом открыть камеру и добавить туда принцесс похищенных в другой вылазке, невозможно. Также Боузер никогда не пытается разместить принцесс, похищенных в одной вылазке, более чем в одной камере.

Марио и Луиджи нашли планы подземелья и владеют информацией о вылазках Боузера. Для каждой вылазки, они хотят определить камеру, в которую будут заточены принцессы.