Training Site
Sideways banner

Chris' Ducks

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 128 megabytes
Time limit: 1.0 seconds

Chris loves ducks.

Grant wants to start giving Chris a duck every day for L days. However, Chris is picky about the ducks he wants to get. More specifically, he only wants to receive one type of duck on any given day, and what type he wants to receive depends on the day. There are five options for the type of duck:

  • Rubber duck (R)
  • Plush duck (P)
  • Digital duck (D)
  • Any option listed above (.)
  • Goose (G)

Unfortunately, Grant only has a limited number of each type of duck. Grant stops giving Chris ducks if he runs out of the right type of duck for a particular day, or if he's already given ducks for L days (ducks cost money after all!).

For how many days can Grant give Chris a duck he wants, if Grant starts on the first day?

Note: For this problem, the term duck is implied to include geese (G) as well unless stated otherwise.


The first line contains an integer L, the number of days where Grant wants to give Chris a duck.

The second line contains four space-separated integers, representing R (number of rubber ducks), P (plush ducks), D (digital ducks), and G (geese) Grant has.

The third line contains a series of letters each representing the type of duck Chris wants to get on each day, with a total length of L. Each letter consists of "R" (rubber duck), "P" (plush duck), "D" (digital duck), "." (any type of duck, except for goose), or "G" (goose).


On the first line, output the number of days where Grant can give Chris a duck.

On the second line, output the number of ducks Grant has left (including geese), after Grant stops giving Chris ducks.


It is guaranteed that 1 \le L \le 500\,000 and 0 \le R, P, D, G \le 500\,000.


  • Subtask 1 (+40%): L\le100, and the types of ducks will not include "." (the letter representing any type of duck).
  • Subtask 2 (+20%): L\le100.
  • Subtask 3 (+40%): No further constaints apply.

Sample explanations

Sample 1

Giving ducks over 8 days means that the ducks used are RPPDPDRG: 2 rubber ducks, 3 plush ducks, 2 digital ducks, and one goose. The duck Chris wants on the 9th day is a plush duck, but we cannot continue because Grant will have run out of plush ducks by then. Grant still has a duck left: 1 rubber duck.

Sample 2

In the first three days, Grant can give Chris any type of duck (as long as it's not a goose). Because he wants to maximise the number of consecutive days he can give Chris a duck, he gives 1 rubber duck and 2 plush ducks for the first three days, before giving his 3 digital ducks for the three days after that. By the end of the 6th day, Grant only has his 5 geese left and so he cannot give Chris what he wants for the 7th day.
Note that this sample won't appear in Subtask 1 as it contains . characters. However, it is a valid test case for Subtasks 2 and 3.

  • Sample Input 1

    3 3 2 1

    Sample Output 1

  • Sample Input 2

    1 2 3 5

    Sample Output 2