LoginSign-Up
마이크로서버
Time Limit: 1 SecMemory Limit: 1024 MiB

문제

당신은 현대자동차그룹의 다양한 부서들이 사용하는 마이크로서비스들이 정상적으로 실행될 수 있도록 클러스터를 관리하는 업무를 맡고 있다.

클러스터는 여러 대의 마이크로서버로 구성되어 있다. 각각의 마이크로서버는 정확히 MiB의 메모리(RAM)를 갖고 있는데, 이 중 MiB는 예비용으로 남겨 두기 때문에, 실제로 애플리케이션들이 사용할 수 있는 메모리는 총 MiB이다.

하나의 마이크로서버에 여러 개의 마이크로서비스를 실행할 수 있는데, 이 때 마이크로서비스들이 사용하는 메모리의 총합은 MiB를 넘을 수 없다.

현재 총 개의 마이크로서비스가 실행 대기중이다. 이 중 번째 서비스는 정확히 MiB의 메모리를 요구한다. 각각의 서비스는 최소 MiB, 최대 MiB의 메모리만을 요구하고 있다.

모든 마이크로서비스들을 실행하기 위해 최소 몇 대의 마이크로서버가 필요한지 구하는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수 가 주어진다. 이후 아래와 같은 형식으로 개의 줄에 개의 테스트 케이스들이 주어진다.

  • 첫 번째 줄에 이 주어진다.
  • 두 번째 줄에 이 공백 하나씩을 사이로 두고 주어진다.
    • 모든 에 대해,
  • 주어지는 모든 수는 정수이다.
  • 주어지는 모든 의 합은 이하이다.

출력

각각의 테스트 케이스에 대해, 한 줄에 하나씩, 순서대로, 필요한 최소 마이크로서버의 수를 출력한다.

서브태스크

번호배점제한
110모든 ()에 대해,
215모든 ()에 대해,
330모든 의 합은 이하이다.
445추가 제약 조건 없음.

노트

  • 예제 1 - 첫 번째 입력: (서비스 1, 서비스 2, 서비스 3) 모두 한 서버에 두면 MiB를 사용하므로 조건을 만족한다.
  • 예제 1 - 두 번째 입력: 두 대의 마이크로서버를 사서, (서비스 1, 서비스 2)를 한 서버에, (서비스 3, 서비스 4)를 다른 서버에 두면 각 서버에서 MiB를 사용하므로 조건을 만족한다.
  • 예제 2 - 세 번째 입력: (서비스 1, 서비스 3), (서비스 2), (서비스 3, 서비스 5)를 각각 한 마이크로서버에서 실행하면, 각각 MiB, MiB, MiB를 사용하여서 조건을 만족한다.
Example Input 1
2
3
300 300 300
4
300 300 300 300
Example Output 1
1
2
Example Input 2
3
2
300 400
2
800 900
5
500 501 350 400 444
Example Output 2
1
2
3
Language-Specific Restrictions