시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 128 MB | 306 | 115 | 74 | 31.624% |
도현이는 TV 퀴즈쇼에 참가했다. 도현이는 총 N개의 문제를 풀어야 하고, 1번부터 차례대로 풀어야 한다.
도현이는 미리 해킹을 통해 모든 문제의 정답을 알고있다. 따라서, 각 문제에 대해서 정답을 맞출지 안 맞출지를 결정할 수 있다.
정답을 맞추면 코인 1개와 그 문제에 해당하는 점수를 받게되고, 맞추지 못하면 지금까지 가지고 있던 모든 코인을 빼앗기고, 그 문제에 해당하는 점수를 감점받는다.
만약, 코인을 M개를 모은다면, 그 문제에 해당하는 보너스 점수를 획득하고 코인을 모두 반납한다.
도현이가 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.
첫째 줄에 문제의 개수 N과 보너스 점수를 얻는데 필요한 코인의 개수 M이 주어진다. (1 ≤ N, M ≤ 500,000)
둘째 줄에는 각 문제에 해당하는 점수가 1번 문제부터 주어지고, 셋째 줄에는 각 문제에 해당하는 보너스 점수가 1번 문제부터 주어진다. 문제의 점수는 1,000보다 작거나 같은 음이 아닌 정수, 보너스 점수는 10,000보다 작거나 같은 음이 아닌 정수이다.
첫째 줄에 도현이가 얻을 수 있는 최대 점수를 출력한다.
5 3 150 20 30 40 50 0 0 0 0 250
500
5 3 1 2 3 16 14 7 0 20 33 66
98
5 5 1 2 3 4 5 0 0 0 2 5
20
5 3 1 2 3 4 5 0 0 0 2 5
16
4 4 998 1 11 23 9998 1 11 23
1056