문제 보기 - King of penalty (kriii1_K)

시간 제한 메모리 제한 제출 횟수 통과한 사람 수 비율
200 ms 16 MiB 99 40 40.4%

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

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

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

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

입력 형식

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

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

출력 형식

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

예제 입력 예제 출력
30 3
2 12 16
2 56