시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 16 MB168736143.571%

문제

어느 날 재의는 기묘한 대회에 참가하게 되었다. 그 이름은 King of penalty! 이 대회는 ICPC와 거의 비슷한 대회인데, 세부적인 규칙은 다음과 같다.

  • 대회는 P분 동안 진행된다. 가장 처음의 페널티 수치는 0이며, 1분이 지날 때마다 1씩 증가한다.
  • 문제를 제출하여 맞추게 되면, 그 문제의 페널티는 소스 제출한 시간의 페널티 수치가 된다. 제출 횟수는 상관없다. 문제를 풀지 않으면 페널티는 0이다. 총 페널티는 모든 문제의 페널티를 더한 값이 된다.
  • 순위는 문제를 많이 푼 팀이 높은 순위를 가지게 된다. 만약 푼 문제 수가 같다면 페널티를 더 많이 받은 팀이 높은 순위를 가지게 된다.

드디어 대회가 시작되었다! 재의는 문제를 받는 순간에 이 대회에서는 N개의 문제가 출제되었고, 각 문제마다 몇 분을 투자하면 풀 수 있는지 분석을 완료했다. 재의는 코딩머신이기 때문에 소스가 틀리는 일 따위 없으며, 또한 남자이기 때문에 한번 작성을 시작한 소스는 작성을 완료하고 나서야 다른 소스를 작성한다. 재의가 소스를 제출하는데 걸리는 시간은 0초이므로 이에 관해서는 신경 쓸 필요 없다.

예를 들어 P=30, N=3이고 각 문제를 푸는 시간이 2분, 12분, 16분 이라고 하자. 그리고 재의가 2분, 12분, 16분 걸리는 문제 순서대로 소스를 작성한다고 하면, 재의가 첫 번째로 푼 문제의 페널티는 2, 두 번째로 푼 문제의 페널티는 14, 이 될 것이고, 마지막 문제는 작성이 끝난 시간이 딱 30분이기 때문에 대회가 이미 끝나서 제출을 하지 못한다. 그러므로 재의는 총 두 문제를 풀고, 페널티는 16이 되는 것이다. 이 방법은 가장 많은 문제를 푸는 방법이기는 하지만, 가장 많은 페널티를 받는 방법은 아니다. 가장 페널티를 많이 받는 방법은 대회 시작 15분이 되었을 때부터 시작하여, 12분이 걸리는 문제와 2분이 걸리는 문제를 차례대로 해결하는 것이다. 그렇게 되면 총 페널티는 56이 되어 최대가 된다.

입력

첫 번째 줄에 대회의 시간 P (1 ≤ P ≤ 109)와 문제의 개수 N (1 ≤ N ≤ 100,000)이 공백으로 구분되어 주어진다.

두 번째 줄에는 N개의 정수가 공백으로 구분되어 주어지는데, 이는 각 문제를 재의가 해결하는데 걸리는 시간이다. 각 정수는 0 이상 P 미만이다.

출력

재의가 대회 시간 내에 최대로 많이 풀 수 있는 문제의 수와 그 때 최대로 받을 수 있 는 페널티의 수치를 출력한다.

예제 입력 1

30 3
2 12 16

예제 출력 1

2 56

출처

Contest > kriiicon > 제1회 kriiICPC K번

  • 문제를 만든 사람: august14
  • 문제의 오타를 찾은 사람: mixnuts