만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

과부하 방지

면접 대비

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

요약
전원 연장선의 콘센트 수, 벽면 콘센트 K개, 기기별 연장선 단계 제한이 주어질 때 전원을 받을 수 있는 기기의 최대 개수를 구합니다.
난이도

보통10점 중 5점

유형
그리디, 정렬, 시뮬레이션
정답자
아직 제출이 없습니다

문제

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

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

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

입력

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

둘째 줄에 각 멀티탭의 소켓 수를 나타내는 NN개의 정수 A1,⋯ ,ANA_1, \cdots, A_N이 공백으로 구분되어 주어집니다. (1≤Ai≤200 0001 \le A_i \le 200\,000)

셋째 줄에 벽 콘센트에서 각 전자기기까지 거칠 수 있는 멀티탭의 최대 개수를 나타내는 MM개의 정수 D1,⋯ ,DMD_1, \cdots, D_M이 공백으로 구분되어 주어집니다. 전자기기까지 거친 멀티탭의 개수는 전류가 기기에 닿기까지 지나는 멀티탭의 개수입니다. (0≤Di≤200 0000 \le D_i \le 200\,000)

Di=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