물건 포장하기
시간 제한1초메모리 제한512 MB
각 트럭이 같은 n개의 물건을 같은 순서로 싣고 R대가 도착할 때, 물건을 순서대로 상자에 담을 때 필요한 길이 B 상자의 총 개수를 구한다.
문제
Albert는 Alice의 가게에서 물건을 포장해 우편으로 부치는 일을 도와주기로 했다. 포장은 번거롭지만 간단하다.
우선 길이가 B로 같은 상자를 여러 개 준비한다. 몇 개를 준비해야 충분한지 계산하는 것이 Albert의 일이다. 하루 동안 총 R대의 트럭이 공장에서 가게로 물건을 배달하는데, 한 번에 한 대의 트럭에서 물건을 모두 받은 뒤 다음 트럭에서 물건을 받는다. 각 트럭은 모두 똑같이 n개의 물건을 배달하며, 각 물건에는 1번부터 n번까지 고유한 번호가 붙어 있어서 번호 순서대로 물건을 꺼내야 한다. i번째 물건의 길이를 v[i]라 하자.
아래 그림은 R = 4, n = 3, v = [2, 2, 3]인 경우를 보여준다. 즉 각 트럭에 길이가 2, 2, 3인 물건이 실려 있고, 이 순서로 (왼쪽에서 오른쪽으로) 물건을 꺼낸다고 생각하면 된다.
Albert는 이 물건들을 길이가 B인 상자에 순서대로 넣어 잘 포장한 뒤 목적지로 부치려 한다. 단, 앞서 말한 대로 1번 트럭부터 R번 트럭까지, 그리고 각 트럭에서는 물건 번호 순서대로 물건을 꺼내서 넣어야 한다.
예를 들어 B = 5이면 위 예제에는 상자가 모두 여섯 개 필요하다. 아래 그림은 왼쪽부터 순서대로 여섯 개의 상자에 Albert가 물건을 채운 모습을 나타낸다.
- 먼저 1번 트럭에서 1번과 2번 물건을 꺼내 첫 번째 상자에 담는다. 3번 물건을 넣기에는 상자의 길이가 모자라므로 두 번째 상자가 필요하다.
- 두 번째 상자에는 1번 트럭에서 꺼낸 3번 물건과 2번 트럭에서 꺼낸 1번 물건을 넣을 수 있다.
- 세 번째 상자에는 2번 트럭에서 꺼낸 2번과 3번 물건을 넣을 수 있다.
- 네 번째 상자에는 3번 트럭에서 꺼낸 1번과 2번 물건을 넣을 수 있다.
- 다섯 번째 상자에는 3번 트럭에서 꺼낸 3번 물건과 4번 트럭에서 꺼낸 1번 물건을 넣을 수 있다.
- 마지막 여섯 번째 상자에는 4번 트럭에서 꺼낸 2번과 3번 물건을 넣을 수 있다.
- 따라서 이 경우 상자가 모두 여섯 개 필요하다.
Albert는 트럭이 배달을 시작하기 전에 상자가 몇 개나 필요할지 미리 계산해서 Alice에게 알려주어야 한다.
n, B, R과 물건의 길이를 나타내는 v 값들이 주어졌을 때, 길이가 B인 상자가 모두 몇 개 필요한지 계산해보자.
입력
첫 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄에 걸쳐 주어진다.
테스트 케이스의 첫 줄에 n, B, R이 주어진다. 둘째 줄에 물건의 길이를 나타내는 n개의 정수가 공백으로 구분되어 주어진다.
출력
각 테스트 케이스의 정답을 각 줄에 출력한다.
제한
- 1 ≤ T ≤ 10
- 1 ≤ n, B ≤ 4,000
- (각 물건 i에 대하여) 1 ≤ v[i] ≤ B
- 1 ≤ R ≤ 10^15