과부하 방지
면접 대비시간 제한1초메모리 제한1024 MB
전원 연장선의 콘센트 수, 벽면 콘센트 K개, 기기별 연장선 단계 제한이 주어질 때 전원을 받을 수 있는 기기의 최대 개수를 구합니다.
문제
이사를 온 은하는 대의 전자기기와 대의 멀티탭을 새 집에 옮겼습니다. 멀티탭의 길이는 무한합니다.
새 집에는 개의 벽면 콘센트가 있습니다(). 은하는 가져온 멀티탭을 활용해 전자기기에 전기를 연결하려고 합니다. 멀티탭은 다른 멀티탭의 소켓에 꽂아도 됩니다. 다만 일부 기기는 전력 사용량이 많아서, 콘센트에서 기기까지 일정 수를 초과하는 멀티탭을 거치면 과부하가 걸려 불이 날 수도 있습니다.
이런 상황에서 최대한 많은 전자기기에 전기를 공급할 수 있나요?
입력
첫 줄에 멀티탭의 수 , 벽 콘센트의 수 , 전기를 연결하고자 하는 전자기기의 수 이 공백으로 구분되어 주어집니다. (, )
둘째 줄에 각 멀티탭의 소켓 수를 나타내는 개의 정수 이 공백으로 구분되어 주어집니다. ()
셋째 줄에 벽 콘센트에서 각 전자기기까지 거칠 수 있는 멀티탭의 최대 개수를 나타내는 개의 정수 이 공백으로 구분되어 주어집니다. 전자기기까지 거친 멀티탭의 개수는 전류가 기기에 닿기까지 지나는 멀티탭의 개수입니다. ()
인 전자기기는 벽 콘센트에만 연결할 수 있습니다.
출력
가능한 한 많은 기기에 전기를 공급할 때, 전기를 공급받는 기기의 수를 출력하세요.