윌리엄은 다가오는 휴가를 계획 중입니다. 그가 휴가를 갈 때마다 반복적으로 겪는 문제는 바로 피로와 맞서야 한다는 점입니다. 어떤 날은 활동을 너무 많이 해서 피로가 감당할 수 있는 수준을 넘어서는 바람에 별로 즐기지 못합니다.
이번에는 윌리엄에게 한 가지 아이디어가 떠올랐습니다. 그는 각 관광 활동이 자신의 컨디션에 미치는 영향을 미리 예측해 보기로 했습니다. 그는 어떤 활동들(예를 들어 운동이나 하이킹 같은 것들)은 피로를 유발하며 자신의 컨디션(기력)을 소모한다는 사실을 깨달았습니다. 반면에 연극이나 뮤지컬 같은 다른 활동들은 활력을 주며 컨디션을 회복시켜 준다고 생각했습니다.
보다 정확히 말하자면, 윌리엄은 D만큼의 초기 컨디션을 가지고 있고, 활동들을 두 가지 그룹으로 나누었습니다.
C개의 피로를 유발하는 활동들과 R개의 활력을 주는 활동들입니다.
각 피로 유발 활동은 일정량의 컨디션을 필요로 하며, 수행 시 그만큼의 컨디션이 소모됩니다.
각 활력 회복 활동은 수행 시 일정량의 컨디션을 회복시켜 줍니다.
또한 윌리엄은 두 그룹의 활동들을 자신의 선호 순서대로 정렬해 두었습니다. 이는 그가 어떤 활동을 더 선호하고 먼저 하고 싶어하는지를 나타냅니다. 중요한 점은 두 그룹의 활동들을 서로 섞어서 수행할 수는 있지만, 그룹 내에서는 앞에 있는 활동을 건너뛰고 뒤에 있는 활동을 먼저 수행하는 일은 절대 하지 않는다는 점입니다. 즉, 한 그룹의 활동을 할 때는 앞에 있는 것부터 차례대로만 수행합니다.
휴가 중 다음에 어떤 활동을 할지를 결정할 때, 윌리엄은 다음과 같은 방식으로 선택합니다:
아직 수행하지 않은 피로 유발 활동 중 첫 번째 활동을, 현재 컨디션이 그 활동에 필요한 양 이상일 경우에만 수행합니다.
만약 현재 컨디션이 부족하다면, 아직 남은 활력 회복 활동이 있다면 그 중 첫 번째 것을 수행하여 컨디션을 회복합니다.
자연스럽게, 더 이상 피로 유발 활동이 남아 있지 않다면, 남은 활력 회복 활동은 모두 수행할 수 있습니다.
이 과정을 고려했을 때, 윌리엄은 총 몇 개의 활동(피로 유발 및 활력 회복 모두 포함)을 수행할 수 있을지를 여러분에게 물어보았습니다.
입력
입력의 첫 줄에는 세 개의 정수 D, C, R이 주어집니다. 이는 각각
초기 컨디션의 양, 피로 유발 활동의 수, 활력 회복 활동의 수를 나타냅니다.
(1 <= D <= 10^5, 1 <= C <= 10^4, 1 <= R <= 10^4)
다음 C줄에는 정수 Ci가 한 줄에 하나씩 주어지며,
이는 각 피로 유발 활동이 필요한 컨디션 양을 선호 순서대로 나타냅니다.
(1 <= Ci <= 10^5)
그다음 R줄에는 정수 Ri가 한 줄에 하나씩 주어지며,
이는 각 활력 회복 활동이 회복시켜 주는 컨디션 양을 선호 순서대로 나타냅니다.
(1 <= Ri <= 10^5)
출력
윌리엄이 수행할 수 있는 총 활동 수를 정수 하나로 출력하세요.
(피로 유발과 활력 회복 활동을 모두 포함한 수)
blackbee4 1년 전 3
윌리엄은 다가오는 휴가를 계획 중입니다. 그가 휴가를 갈 때마다 반복적으로 겪는 문제는 바로 피로와 맞서야 한다는 점입니다. 어떤 날은 활동을 너무 많이 해서 피로가 감당할 수 있는 수준을 넘어서는 바람에 별로 즐기지 못합니다.
이번에는 윌리엄에게 한 가지 아이디어가 떠올랐습니다. 그는 각 관광 활동이 자신의 컨디션에 미치는 영향을 미리 예측해 보기로 했습니다. 그는 어떤 활동들(예를 들어 운동이나 하이킹 같은 것들)은 피로를 유발하며 자신의 컨디션(기력)을 소모한다는 사실을 깨달았습니다. 반면에 연극이나 뮤지컬 같은 다른 활동들은 활력을 주며 컨디션을 회복시켜 준다고 생각했습니다.
보다 정확히 말하자면, 윌리엄은 D만큼의 초기 컨디션을 가지고 있고, 활동들을 두 가지 그룹으로 나누었습니다.
C개의 피로를 유발하는 활동들과 R개의 활력을 주는 활동들입니다.
각 피로 유발 활동은 일정량의 컨디션을 필요로 하며, 수행 시 그만큼의 컨디션이 소모됩니다.
각 활력 회복 활동은 수행 시 일정량의 컨디션을 회복시켜 줍니다.
또한 윌리엄은 두 그룹의 활동들을 자신의 선호 순서대로 정렬해 두었습니다. 이는 그가 어떤 활동을 더 선호하고 먼저 하고 싶어하는지를 나타냅니다. 중요한 점은 두 그룹의 활동들을 서로 섞어서 수행할 수는 있지만, 그룹 내에서는 앞에 있는 활동을 건너뛰고 뒤에 있는 활동을 먼저 수행하는 일은 절대 하지 않는다는 점입니다. 즉, 한 그룹의 활동을 할 때는 앞에 있는 것부터 차례대로만 수행합니다.
휴가 중 다음에 어떤 활동을 할지를 결정할 때, 윌리엄은 다음과 같은 방식으로 선택합니다:
아직 수행하지 않은 피로 유발 활동 중 첫 번째 활동을, 현재 컨디션이 그 활동에 필요한 양 이상일 경우에만 수행합니다.
만약 현재 컨디션이 부족하다면, 아직 남은 활력 회복 활동이 있다면 그 중 첫 번째 것을 수행하여 컨디션을 회복합니다.
자연스럽게, 더 이상 피로 유발 활동이 남아 있지 않다면, 남은 활력 회복 활동은 모두 수행할 수 있습니다.
이 과정을 고려했을 때, 윌리엄은 총 몇 개의 활동(피로 유발 및 활력 회복 모두 포함)을 수행할 수 있을지를 여러분에게 물어보았습니다.
입력
입력의 첫 줄에는 세 개의 정수 D, C, R이 주어집니다. 이는 각각
초기 컨디션의 양, 피로 유발 활동의 수, 활력 회복 활동의 수를 나타냅니다.
(1 <= D <= 10^5, 1 <= C <= 10^4, 1 <= R <= 10^4)
다음 C줄에는 정수 Ci가 한 줄에 하나씩 주어지며,
이는 각 피로 유발 활동이 필요한 컨디션 양을 선호 순서대로 나타냅니다.
(1 <= Ci <= 10^5)
그다음 R줄에는 정수 Ri가 한 줄에 하나씩 주어지며,
이는 각 활력 회복 활동이 회복시켜 주는 컨디션 양을 선호 순서대로 나타냅니다.
(1 <= Ri <= 10^5)
출력
윌리엄이 수행할 수 있는 총 활동 수를 정수 하나로 출력하세요.
(피로 유발과 활력 회복 활동을 모두 포함한 수)