Задача А. Акции
Задачу добавил: alef
Успешно сдано решений: 4
Телефон Стива продолжал звонить. Отвечать Стив не собирался: за последние несколько дней ему уже порядком надоело сообщать очередному агенту, что он не планирует продавать акции 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