과부하 방지

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

요약
각 멀티탭의 소켓 수와 기기별로 허용되는 최대 멀티탭 개수가 주어질 때, 전원을 공급받을 수 있는 기기의 최대 개수를 구한다.
난이도

보통10점 중 7점

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

문제

이사를 온 은하는 마침내 MM대의 전자기기와 NN대의 멀티탭을 모두 새 집에 옮겼습니다. 멀티탭의 길이는 무한합니다.

새 집에는 KK개의 벽면 콘센트가 있습니다. (K≤M)(K \le M) 은하는 가져온 멀티탭을 활용해 전자기기들에 전기를 연결하려고 합니다. 어떤 멀티탭을 다른 멀티탭 소켓에 꽂아도 됩니다. 다만 일부 기기는 전력 사용량이 많아서, 전기가 콘센트로부터 기기까지 일정 수 초과의 멀티탭을 거치는 경우 전자기기에 과부하가 걸려 불이 나게 될 수도 있습니다.

이런 상황에서 최대한 많은 대수의 전자기기에 전기를 공급받을 수 있게 할 수 있나요?

입력

첫 줄에 멀티탭의 수 NN, 벽 콘센트의 수 KK, 전기를 연결하고자 하는 전자기기의 수 MM이 공백으로 구분되어 주어집니다. (1≤N≤200,000;(1 \le N \le 200\\,000; 1≤K≤M≤200,000)1 \le K \le M \le 200\\,000)

둘째 줄에 각 멀티탭의 소켓 수를 의미하는 NN개의 정수 A_1,⋯ ,A_NA\_1,\cdots,A\_N이 공백으로 구분되어 주어집니다. (1≤A_i≤200,000)(1 \le A\_i \le 200\\,000)

셋째 줄에 벽 콘센트로부터 각 전자기기까지 몇 개까지의 멀티탭을 거칠 수 있는지를 의미하는 MM개의 정수 D_1,⋯ ,D_MD\_1,\cdots,D\_M이 공백으로 구분되어 주어집니다. 전자기기로 가는데 걸친 멀티탭의 개수는, 전자기기까지 전류가 흐르는 동안 만나는 멀티탭의 개수입니다. (0≤D_i≤200,000)(0 \le D\_i \le 200\\,000)

D_i=0D\_i=0인 전자기기는 벽 콘센트에만 연결할 수 있습니다.

출력

주어진 상황에서 가능한 한 많은 장치들이 전기를 공급받을 수 있게 할 때, 전기를 공급받게 되는 장치의 수를 출력하세요.

예제2

  1. 예제 1

    입력
    3 1 10
    1 2 3
    3 1 4 1 5 9 2 6 5 3
    
    예상 출력
    4
    
  2. 예제 2

    입력
    2 2 6
    2 4
    2 4 0 2 0 3
    
    예상 출력
    5