9785번 - Damage Over Time 다국어

문제

In many MMORPGs (Massively Multiplayer Online Role-Playing Games), damage over time (DoT) is one of the good ways for the attacker to deal damage on enemies. For example, a rogue in World of Warcraft (WoW) may apply a poison to his knife and then stab it on an enemy using “Garrote” ability. Both poison and garrote offer the damage over time. For example, poison deals 10 damages per second for 10 seconds and garrote deals 20 damages per second for 5 seconds. That is, “stacking” as many DoT as possible on enemy certainly results in great total damages.

Here is the problem. You are required to write a program, for a set of provided DoT abilities, to calculate the possible maximum DoT and the maximum length of time of such DoT to be hold. In the example above, the possible maximum DoT is 30 damages for 5 seconds.

입력

The first line of the input includes integer N (0 < N < 100) indicating the number of abilities and integer M (0 < M < 100, M ≤ N) indicating how many abilities can be “stacked up” at one time. Then, each ability is input by its damage per seconds and its length (seconds), one ability per one line.

출력

Print out the maximum DoT being possible to apply to an enemy using the provided set of abilities and the length of time such maximum DoT hold.

제한

힌트