Поскольку погода устроителей так и продолжает не радовать, они планируют использовать рулонный газон.

Дорожка для забега на роликах имеет длину n метров. Устроители очень тщательно готовятся к чемпионату, поэтому они поделили её на участки длиной 1 метр и для каждого такого участка провели исследование почвы. Оказалось, что придётся использовать два вида газона. Для определённости будем называть их A и B.

Компания, которая будет выполнять работы, укладывает один метр газона вида A за p₁ денежных единиц, а один метр газона вида B за p₂ денежных единиц. Однако если заказать укладку d₁ или более метров газона вида A подряд, то один метр обойдётся немного дешевле: s₁ денежных единиц. Для газона вида B тоже есть оптовая скидка: если заказать укладку d₂ или более метров этого газона подряд, то один метр будет стоить s₂ денежных единиц.

Устроители располагают картой дорожки для забега, на которой каждый участок помечен символом A, если на нём допустимо использовать только газон вида A, символом B, если допустимо использовать только газон вида B, и символом 0, если можно использовать как газон вида A, так и газон вида B.

Ваша задача — определить минимальную стоимость работ по покрытию дорожки газоном.