Pharmacy

Many pharmacies in the United States fill prescriptions strictly on a first-come, first-served basis. Some even prefer prescriptions sent electronically from a remote site over prescriptions dropped off by customers waiting in the store. As a result, customers often wait for their prescriptions because technicians are busy filling prescriptions that may not be picked up for a long time.

This problem studies the effect of an "in-store customers first" policy. Under this policy, technicians fill prescriptions in the order they are dropped off, but they do not start filling remote prescriptions while in-store prescriptions are still waiting.

Write a program that computes the average completion time for in-store and remote customers under this policy.

The first line contains two integers $n$ ($0 < n \le 100\,000$) and $T$ ($0 < T \le 10$), where $n$ is the number of prescriptions and $T$ is the number of technicians.

Each of the next $n$ lines contains one prescription. A line has an integer $d$ ($0 < d \le 10^9$), the time in seconds when the prescription was dropped off, followed by the character 'R' (remote) or 'S' (in-store), followed by an integer $k$ ($0 < k \le 500$), the number of seconds a technician needs to fill it.

Prescriptions are listed in increasing order of drop-off time. If several prescriptions are dropped off at the same time, in-store prescriptions come first regardless of their order in the input. If two prescriptions of the same type are dropped off at the same time, the one with the shorter fill time is filled first.

Once a technician starts a prescription, the technician finishes it, even if an in-store prescription is dropped off in the meantime. Each prescription needs one technician, and each technician works on one prescription at a time. A technician who finishes a prescription starts the next one immediately. Time spent choosing the next prescription is ignored. The technicians keep working until all prescriptions are filled.

Output two numbers $o$ and $r$, the average completion times for in-store and remote prescriptions. A completion time is the difference between the drop-off time and the time the prescription is filled.

If the input has no in-store prescriptions, output $0$ for $o$. If it has no remote prescriptions, output $0$ for $r$. An answer is accepted if its relative or absolute error is within $10^{-6}$.