Влад нашёл полоску из \(n\) клеток, пронумерованных слева направо от \(1\) до \(n\). На \(i\)-й клетке записаны положительное целое число \(a_i\) и буква \(s_i\), все \(s_i\) равны либо 'L' либо 'R'.
Влад предлагает вам попробовать набрать максимально возможное количество очков, сделав любое (возможно нулевое) количество операций.
За одну операцию вы можете выбрать два индекса \(l\) и \(r\) (\(1 \le l < r \le n\)), такие что \(s_l\) = 'L' и \(s_r\) = 'R' и сделать следующее:
- прибавить к текущему счёту \(a_l + a_{l + 1} + \dots + a_{r - 1} + a_r\) очков;
- заменить \(s_i\) на '.' для всех \(l \le i \le r\), то есть выбирать эти индексы вы больше не сможете.
Для примера рассмотрим следующую полоску:
| \(3\) | \(5\) | \(1\) | \(4\) | \(3\) | \(2\) |
| L | R | L | L | L | R |
Можно сначала выбрать \(l = 1\), \(r = 2\) и добавить к своему счёту \(3 + 5 = 8\)
| \(3\) | \(5\) | \(1\) | \(4\) | \(3\) | \(2\) |
| . | . | L | L | L | R |
Затем выбрать \(l = 3\), \(r = 6\) и прибавить к счёту \(1 + 4 + 3 + 2 = 10\)
| \(3\) | \(5\) | \(1\) | \(4\) | \(3\) | \(2\) |
| . | . | . | . | . | . |
В результате невозможно выполнить ещё одну операцию, а итоговый счёт равен \(18\).
Какой максимальный счёт можно набрать?