수족관의 점검 시간표

문제

수족관은 앞으로 N일 동안 사용할 수 있는 점검 시간표를 받았다. 수족관에는 번호가 1부터 N까지인 점검 작업이 하나씩 있다. i번 작업은 반드시 i일이 끝나기 전에 완료해야 하며, 완료하는 데 필요한 작업 시간은 D_i단위다. 모든 작업의 내용과 준비물은 첫날이 시작되기 전에 마련되어 있으므로, 마감일보다 먼저 작업을 시작하거나 완료해도 된다. 수족관이 i일에 점검에 사용할 수 있는 시간은 C_i단위다. 이 시간은 해당 날짜에만 사용할 수 있으며, 사용하지 않은 시간을 다음 날로 넘길 수 없다. 하루에 여러 작업을 진행해도 되지만, 그날 진행한 작업 시간의 합은 C_i를 넘을 수 없다. 모든 작업 시간은 정수 단위로 배정한다. 한 작업을 여러 날에 나누어 진행하거나, 다른 작업을 진행한 뒤 중단했던 작업을 이어서 진행해도 된다. 예를 들어 3단위가 필요한 작업에 첫날 1단위, 셋째 날 2단위를 배정하면 셋째 날에 완료된다. 각 작업은 필요한 시간을 모두 배정했을 때만 완료한 것으로 인정된다. 일부 시간만 배정한 작업이나 마감일을 지난 뒤 완료한 작업은 실적에 포함하지 않는다. 작업마다 완료했을 때 얻는 실적은 모두 같다. 따라서 어려운 작업을 포기하고 여러 개의 짧은 작업을 완료하는 편이 유리할 수도 있다. 어떤 작업을 포기할지는 자유롭게 정할 수 있다. 점검에 필요한 시간들과 날짜별로 사용할 수 있는 시간이 주어진다. 모든 날짜의 시간 제한과 각 작업의 마감일을 지키면서 완료할 수 있는 작업 수의 최댓값을 구한다. 최댓값을 만드는 시간표가 여러 개여도 작업 번호나 실제 시간표를 출력할 필요는 없다. 완료할 수 있는 작업이 하나도 없다면 최댓값은 0이다.

입력

첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 200,000)
둘째 줄에 길이가 N인 문자열 D가 주어진다. 각 문자는 '1'부터 '9' 중 하나이며, i번째 문자가 나타내는 정수가 D_i다. (1 ≤ D_i ≤ 9)
셋째 줄에 길이가 N인 문자열 C가 주어진다. 각 문자는 '0'부터 '9' 중 하나이며, i번째 문자가 나타내는 정수가 C_i다. (0 ≤ C_i ≤ 9)
두 문자열 안에는 공백이 없다.

출력

완료할 수 있는 작업 수의 최댓값을 정수 하나로 출력한다. 완료할 수 있는 작업이 없다면 0을 출력한다.

6
413222
021012

3

5
11111
00000

0

7
9231111
9000000

6

출처: Devin.KR 자체 제작