만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

항해

시간 제한1초메모리 제한1024 MB

요약
샌드위치 N개에서 X cm 이상 Y cm 이하의 조각을 잘라 먹을 수 있는 최대 끼니 수를 구하고, 그때 버려지는 조각 길이의 합을 최소로 구하는 문제입니다.
난이도

보통10점 중 6점

유형
그리디, 정렬, 이분 탐색
정답자
아직 제출이 없습니다

문제

준원이는 오늘부터 항해를 시작한다. 준원이에게 남은 식량은 서브웨이 샌드위치 NN개뿐이다. ii번째 샌드위치의 길이는 AiA_i cm이다.

준원이는 매 끼니마다 샌드위치를 조금씩 잘라 먹는다. 구체적으로, NN개의 샌드위치 중 하나를 골라 XX cm 이상 YY cm 이하의 길이로 잘라 먹는다. 자르고 남은 부분이 XX cm 미만이면 준원이는 그 조각을 버린다. (준원이는 여러 개의 작은 조각을 모아서 먹는 구차한 행동은 하지 않는다.)

가지고 있는 샌드위치로 해결할 수 있는 끼니 수의 최댓값을 구하라. 그리고 그만큼의 끼니를 해결한 뒤 버려지는 샌드위치 조각 길이의 합의 최솟값을 구하라.

입력

첫째 줄에 NN, XX, YY가 공백으로 구분되어 주어진다.

둘째 줄에 각 샌드위치의 길이 A1,A2,⋯ ,ANA_1, A_2, \cdots, A_N이 공백으로 구분되어 주어진다.

출력

첫째 줄에는 준원이가 해결할 수 있는 끼니 수의 최댓값을 출력한다.

둘째 줄에는 버려지는 샌드위치 조각 길이의 합의 최솟값을 출력한다.

제한

  • 1≤N≤40 0001 \le N \le 40\,000
  • 1≤X≤Y≤40 0001 \le X \le Y \le 40\,000
  • 각 ii (1≤i≤N1 \le i \le N)에 대해, 1≤Ai≤40 0001 \le A_i \le 40\,000.

예제1

  1. 예제 1

    입력
    6 10 12
    11 10 17 5 23 28
    
    예상 출력
    7
    14