Contest.uni-smr.ac.ru :: соревнования по программированию
Русская версия || English version
Login:
Password:
Забыли пароль?
 пример поиска: Вася Пупкин
 






Задача А. Акции

Задачу добавил: alef

Успешно сдано решений: 4

Ограничение по времени на тест:2 секунды
Ограничение по памяти на тест: 256 мегабайт

Телефон Стива продолжал звонить. Отвечать Стив не собирался: за последние несколько дней ему уже порядком надоело сообщать очередному агенту, что он не планирует продавать акции Gadget Operating System. Да, акции стремительно падают в цене, но Стиву они достались случайно и бесплатно, и он никогда не думал о них, как об инвестиции. Впрочем, наблюдая за сводками с биржи, он поймал себя на мысли, что мог бы немного заработать. Конечно, если бы обладал даром предвидения.

В параллельной вселенной, где Стив наделён даром предвидения, правила таковы.

Стив не намерен вкладывать дополнительные деньги в акции. Его начальный капитал — n акций, денег у него нет.

Агенты только скупают акции, но не продают их. На бирже Стив может только покупать акции.

В каждый момент времени Стив может либо продавать акции, либо покупать их, либо ничего с акциями / деньгами не делать.

Стив продаёт и покупает акции пакетом: либо он продаёт агенту все имеющиеся у него акции, либо покупает на бирже максимально возможное целое число акций на все имеющиеся у него деньги. После покупки у него может остаться какая-то сумма, строго меньшая цены одной акции в момент покупки. При следующей покупке эта сумма может быть использована.

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

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

В первой строке содержатся целые числа n и m (1 ≤ n ≤ 109, 1 ≤ m ≤ 5 × 105) — количество акций у Стива и количество моментов времени, в которые он мог совершать операции с акциями или деньгами.

Во второй строке содержится m целых чисел a1, a2, ..., am через пробел (1 ≤ aj ≤ 109) — цены за одну акцию, которые предлагали Стиву агенты.

В третьей строке содержится m целых чисел b1, b2, ..., bm через пробел(1 ≤ bj ≤ 109) — цены за одну акцию в эти же моменты на бирже.

Гарантируется, что входные данные таковы, что ни в какой момент времени Стив не может обладать более, чем 1018 акций, или суммой денег, превосходящей 1018.

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

В первой строке выведите целое число s — максимально возможную сумму, которую Стив мог бы заработать. Гарантируется, что она не превышает 1018.

Во второй строке выведите последовательность из m символов A, B, 0 (ноль), обозначающих соответственно продажу Стивом акций агенту, покупку акций на бирже и отсутствие каких-либо транзакций. Если существует несколько оптимальных последовательностей действий, выведите любую из них.

Примеры

Входные данные
20 6
4 6 9 7 5 3
3 3 6 5 4 3
Выходные данные
236
ABA000
Входные данные
10 5
1 2 3 4 5
5 4 3 2 1
Выходные данные
75
00ABA

Сдать задачу

Задать вопрос жюри по этой задаче