Податки

Обмеження: 2 сек., 256 МіБ

Скоро жовтень — ФОПам треба буде подавати податкову декларацію за третій квартал. Ти ж, студенте, не приховуєш свого доходу від держави та сплачуєш податки ?

Є дві системи оподаткування: загальна та спрощена. Загальна система характеризується параметрами \(k_1\), \(b_1\), а спрощена — \(k_2\), \(b_2\). На загальній системі за отримання доходу \(x\) треба сплатити податок у розмірі \(k_1 x + b_1\), а на спрощеній — \(k_2 x + b_2\).

ФОП Зеник перебуває на одній із систем оподаткування. Він щомісяця вибирає залишитися на тій системі, на якій є, або перейти на іншу з урахуванням обмежень.

• У перший місяць роботи можна вибрати будь-яку систему оподаткування.

• Із спрощеної на загальну систему можна перейти на початку будь-якого місяця.

• Якщо підприємець на загальній системі не перебував на спрощеній раніше, він може на початку будь-якого місяця перейти на спрощену систему.

• Після переходу із спрощеної на загальну систему назад на спрощену можна повернутися, тільки перебувши \(m\) місяців на загальній.

Зеник знає, який у нього буде дохід протягом наступних \(n\) місяців — \(a_i\) в \(i\)-ий місяць.

Допоможи йому знайти стратегію, що мінімізує суму сплачених податків.

Вхідні дані

У першому рядку задано два цілі числа \(n\) і \(m\) — кількість місяців, для яких треба знайти стратегію, і кількість місяців, протягом яких треба перебути на загальній системі оподаткування перед поверненням назад на спрощену.

У другому рядку записано чотири цілі числа \(k_1\), \(b_1\), \(k_2\), \(b_2\) — параметри, що задають загальну й спрощену системи.

У третьому рядку задано \(n\) цілих чисел \(a_i\) — дохід Зеника в наступні \(n\) місяців.

Вихідні дані

У першому рядку виведи ціле число — мінімальну суму сплачених податків за \(n\) місяців.

У другому рядку виведи \(n\) чисел 1 і 2 без пропусків. \(i\)-е число повинне дорівнювати 1, якщо у твоїй стратегії в \(i\)-ий місяць Зеник буде перебувати на загальній системі оподаткування, і 2 — якщо на спрощеній.

Обмеження

\(1 \le m < n \le 10^5\),

\(0 \le k_1, k_2 \le 10^6\),

\(0 \le b_1, b_2 \le 10^{12}\),

\(0 \le a_i \le 10^6\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 2 4 74 7 47 6 12 14 13 1 10 15 5 10 2 16	1167 21112112221

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
11 2 7 47 4 74 6 12 14 13 1 10 15 5 10 2 16	1170 12221121112

Примітки

У першому прикладі Зеник буде на загальній системі в другому, третьому, четвертому, шостому, сьомому та одинадцятому місяцях, а на спрощеній — у першому, п’ятому, восьмому, дев’ятому та десятому.