새 앨범
시간 제한2초메모리 제한128 MB
곡 길이와 CD 용량이 주어지고 13으로 나누어지는 곡 수를 금지할 때 모든 곡을 담는 데 필요한 최소 CD 개수를 구하는 문제입니다.
문제
한 밴드가 같은 길이의 노래 N곡으로 새 앨범을 만들려고 한다. 각 노래의 길이는 L초이고, CD 한 장에는 최대 C초의 음악을 담을 수 있다.
같은 CD에 노래를 두 곡 이상 넣으면, 이웃한 두 노래 사이마다 1초의 공백이 필요하다. 따라서 한 CD에 x곡을 넣는 데 필요한 시간은 x * L + (x - 1)초이다.
또한 미신 때문에 어떤 CD에도 들어 있는 노래 수가 13의 배수이면 안 된다. 모든 N곡을 담기 위해 필요한 CD 장수의 최솟값을 구하시오.
입력
첫째 줄에 노래의 개수 N이 주어진다. N은 100,000 이하의 자연수이다.
둘째 줄에 각 노래의 길이 L이 초 단위로 주어진다.
셋째 줄에 CD 한 장의 용량 C가 초 단위로 주어진다. C는 10,000 이하의 자연수이고, L은 C 이하의 자연수이다.
출력
모든 노래를 담기 위해 필요한 CD 장수의 최솟값을 출력한다.
힌트
첫 번째 공개 테스트에서는 한 CD에 최대 두 곡만 담을 수 있다.