지속 피해 쌓기

MMORPG에서 지속 피해(DoT, damage over time)는 적에게 피해를 주는 좋은 수단이다. 도적은 단검에 독을 바른 뒤 그 단검으로 적을 찔러 목 조르기를 걸 수 있고, 독과 목 조르기는 둘 다 시간에 걸쳐 피해를 준다. 독은 10초 동안 초당 10의 피해를 주고, 목 조르기는 5초 동안 초당 20의 피해를 준다. 이렇게 지속 피해를 최대한 겹쳐 쌓으면 총 피해가 커진다.

능력 $N$개가 주어진다. 능력 $i$는 걸린 순간부터 $t_i$초 동안 초당 $d_i$의 피해를 준다. 고른 능력은 모두 같은 순간에 걸리고, 한 번에 겹칠 수 있는 능력은 최대 $M$개다. 겹친 능력의 초당 피해 합이 가장 커지도록 능력을 고른 다음, 그 최대 초당 피해와 그 피해가 유지되는 시간을 구하는 프로그램을 작성하시오. 고른 능력의 효과가 모두 남아 있는 동안에만 이 피해가 나오므로, 유지 시간은 고른 능력의 지속 시간 중 최솟값이다. 최대 초당 피해를 만드는 조합이 여럿이면 그중 유지 시간이 가장 긴 조합을 답으로 한다.

앞의 예에서 최대 초당 피해는 30이고, 이 피해는 5초 동안 유지된다.

첫째 줄에 능력의 개수 $N$과 한 번에 겹칠 수 있는 능력의 최대 개수 $M$이 주어진다. ($0 < N < 100$, $0 < M < 100$, $M \le N$)

다음 $N$개 줄에 능력이 한 줄에 하나씩 주어진다. 각 줄에는 그 능력의 초당 피해량 $d$와 지속 시간 $t$(초)가 빈칸을 사이에 두고 주어지며, 둘 다 양의 정수다.

주어진 능력으로 적에게 줄 수 있는 최대 초당 피해와 그 피해가 유지되는 시간을 빈칸을 사이에 두고 한 줄에 출력한다.