Distribution of Prize Money
|Time limit:||3.00 s|
|Memory limit:||512 MB|
Syrjälä's most famous programming contest, Syrjälä Open, has been recently held online. The total prize fund of the contest is $x$ Syrjälä dollars.
There were $n$ contestants taking part, and each of them was ranked from $1$-st to $n$-th. No two contestants had the same rank.
Unfortunately, the distribution of prize money among the contestants is not known yet. It's only known that every contestant will receive a non-negative integer amount of Syrjälä dollars, and no contestant will receive less money than another contestant with worse rank.
Some of the contestants are your friends. You've decided to find the least possible part of the prize fund, which will be definitely received by them in total, among all valid distributions of prize money. Also, you are interested in the worst
distribution: the one that leads to the least possible amount of money received by your friends. Write a program to help yourself.
The first line of the input contains a single integer $x$, the total prize fund, in Syrjälä dollars. The second line contains a string of length $n$ consisting of uppercase English letters
only. The $i$-th character of the string equals to
if the contestant ranked $i$-th is your friend, and
Output two lines. The first line must contain the least possible amount of money, which will be definitely received by your friends in total.
The second line must contain a non-increasing sequence of $n$ non-negative integers, the prizes of the contestants ranked first, second, $\ldots, n$-th in the worst distribution of prize money. The sum of these $n$ integers must be equal to $x$. If there are several worst distributions, you may output any of them.
- $1 \le x \le 10^9$
- $1 \le n \le 400$
7 7 3 3 3 0 0
100 0 0 0