نص المسألة

يوجد $N$ مصباحاً مرتبة في صف أفقي، مرقمة من $1$ إلى $N$ من اليسار إلى اليمين. لون كل مصباح هو الأحمر أو الأخضر أو الأزرق. تُعبِّر السلسلة النصية $S$ عن ألوان المصابيح، حيث يكون لون المصباح $i$ ($1 \le i \le N$) أحمر عندما يكون الحرف رقم $i$ في $S$ هو R، وأخضر عندما يكون G، وأزرق عندما يكون B. في البداية، جميع المصابيح مضاءة.

طالما يوجد على الأقل مصباح $1$ مضاء، يمكن لـ JOI-kun إجراء الأنواع الـ $3$ التالية من العمليات بأي ترتيب وبأي عدد من المرات (يُسمح أيضاً بإجراء $0$ عملية):

• دفع $A$ ين لإطفاء المصباح المضاء الواقع في أقصى اليسار.
• دفع $B$ ين لإطفاء المصباح المضاء الواقع في أقصى اليمين.
• دفع $C$ ين لاختيار مصباح $1$ مضاء وإعادة إضاءته بأي لون يريده.

يريد JOI-kun أن يبدو صف المصابيح هذا بلون أبيض جميل عند النظر إليه من بعيد. لتحقيق ذلك، يجب أن يكون تسلسل ألوان المصابيح المضاءة عند النظر إليها من اليسار إلى اليمين تكراراً لـ RGB (أحمر، أخضر، أزرق) مثل RGBRGB...RGB. ومع ذلك، فإن الحالة التي يوجد فيها $0$ مصباح مضاء تُعتبر أيضاً تكراراً لـ RGB. لاحظ أن تسلسلات الألوان مثل GBRGBR أو RGBRG لا تحقق الشرط.

بإعطائك معلومات عن المصابيح والتكاليف اللازمة للعمليات، اكتب برنامجاً لإيجاد أقل مبلغ مالي لازم لجعل تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB.

القيود

• $1 \le N \le 200\,000$.
• $S$ سلسلة نصية طولها $N$.
• كل حرف في $S$ هو R أو G أو B.
• $1 \le A \le 10^9$.
• $1 \le B \le 10^9$.
• $1 \le C \le 10^9$.
• $N, A, B, C$ أعداد صحيحة.

المهام الفرعية

1. ($4$ نقاط) $N = 3$.
2. ($22$ نقطة) $N \le 300$.
3. ($19$ نقطة) $N \le 10\,000$.
4. ($9$ نقاط) $N$ من مضاعفات $3$، $A = 10^9$، $B = 10^9$، $C = 1$.
5. ($10$ نقاط) $A = 10^9$، $B = 10^9$، $C = 1$.
6. ($36$ نقطة) لا توجد قيود إضافية.

الإدخال

يُعطى الإدخال بالصيغة التالية: $N$ $S$ $A \ B \ C$

الإخراج

اطبع في سطر $1$ أقل مبلغ مالي لازم لجعل تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB، مع حذف الوحدة (ين).

أمثلة الإدخال والإخراج

6
GRBBRG
3 4 5

16

على سبيل المثال، عند إجراء $4$ عمليات كما يلي، يصبح تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB. يُرمز للمصباح المطفأ بالرمز -.

1. دفع $3$ ين لإطفاء المصباح $1$، وهو المصباح المضاء في أقصى اليسار. تُوصَف حالة المصابيح بالسلسلة -RBBRG.
2. دفع $4$ ين لإطفاء المصباح $6$، وهو المصباح المضاء في أقصى اليمين. تُوصَف حالة المصابيح بالسلسلة -RBBR-.
3. دفع $4$ ين لإطفاء المصباح $5$، وهو المصباح المضاء في أقصى اليمين. تُوصَف حالة المصابيح بالسلسلة -RBB--.
4. دفع $5$ ين لاختيار المصباح $3$ وإعادة إضاءته باللون الأخضر. تُوصَف حالة المصابيح بالسلسلة -RGB--.

نظراً لاستحالة جعل تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB بدفع أقل من $16$ ين، نطبع $16$.

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 6$.

3
BRG
1000000000 1000000000 1

3

على سبيل المثال، عند إجراء $3$ عمليات كما يلي، يصبح تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB. يُرمز للمصباح المطفأ بالرمز -.

1. دفع $1$ ين لاختيار المصباح $2$ وإعادة إضاءته باللون الأخضر. تُوصَف حالة المصابيح بالسلسلة BGG.
2. دفع $1$ ين لاختيار المصباح $3$ وإعادة إضاءته باللون الأزرق. تُوصَف حالة المصابيح بالسلسلة BGB.
3. دفع $1$ ين لاختيار المصباح $1$ وإعادة إضاءته باللون الأحمر. تُوصَف حالة المصابيح بالسلسلة RGB.

نظراً لاستحالة جعل تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB بدفع أقل من $3$ ين، نطبع $3$.

مثال الإدخال هذا يحقق قيود المهام الفرعية $1, 2, 3, 4, 5, 6$.

3
GRB
9 11 14

27

على سبيل المثال، عند إجراء $3$ عمليات كما يلي، يصبح تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB. يُرمز للمصباح المطفأ بالرمز -.

1. دفع $9$ ين لإطفاء المصباح $1$، وهو المصباح المضاء في أقصى اليسار. تُوصَف حالة المصابيح بالسلسلة -RB.
2. دفع $9$ ين لإطفاء المصباح $2$، وهو المصباح المضاء في أقصى اليسار. تُوصَف حالة المصابيح بالسلسلة --B.
3. دفع $9$ ين لإطفاء المصباح $3$، وهو المصباح المضاء في أقصى اليسار. تُوصَف حالة المصابيح بالسلسلة ---.

نظراً لاستحالة جعل تسلسل ألوان المصابيح المضاءة تكراراً لـ RGB بدفع أقل من $27$ ين، نطبع $27$. لاحظ أن الحالة التي يوجد فيها $0$ مصباح مضاء تحقق الشرط أيضاً.

مثال الإدخال هذا يحقق قيود المهام الفرعية $1, 2, 3, 6$.

9
RGBRGBRGB
1000000000 1000000000 1

0

بما أن تسلسل ألوان المصابيح هو بالفعل تكرار لـ RGB، نطبع $0$.

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 4, 5, 6$.

20
BRGBRGBBGBBBGRRBBBRB
1000000000 1000000000 1

2000000008

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 5, 6$.

23
BBGRGBBBBBBGRRGGGGBGGGG
786820955 792349124 710671229

10107224827

مثال الإدخال هذا يحقق قيود المهام الفرعية $2, 3, 6$.