문제
KOI 한국정보올림피아드 대회에 나가는데 있어서,
알고리즘 공부만으로 부족하다고 생각한 택쌤은 학생들에게 알고리즘과 더불어 갈고리즘도 가르치기로 했다.
갈고리즘은 택쌤만 알고있는 비밀로, 정올 문제를 풀 수 있는 어둠의 방법이다.
어떤 문제는 알고리즘보다 갈고리즘으로 푸는 것이 훨씬 빠르다.
그러나, 연속 두 개의 문제를(예를 들어 3번 문제와 4번 문제를) 갈고리즘으로 풀게 되면,
문제 출제자들의 의심을 살 수 있으므로, 그런 경우는 피해야만 한다.
이번 KOI 대회에는 N개의 문제가 나온다.
각 문제는 하나를 맞출 때마다 100점씩 받으며, 편의상 부분점수는 생각하지 않기로 한다.
대회 제한시간이 K분일 경우,
여러분들이 알고리즘과 갈고리즘을 섞어서 얻을 수 있는 최대의 점수를 출력하는 프로그램을 작성하라.
입력
첫 줄에 N과 K가 주어진다. (1<=N<=5,000, 1<=K<=2,000)
둘째 줄에 N개의 정수가 공백을 사이에 두고 주어지며,
이는 1번부터 N번까지 각 문제를 알고리즘으로 풀 경우 걸리는 시간이다. (각 1이상 2000이하)
셋째 줄에 N개의 정수가 공백을 사이에 두고 주어지며,
이는 1번부터 N번까지 각 문제를 갈고리즘으로 풀 경우 걸리는 시간이다. (각 1이상 2000이하)
어떤 문제는 갈고리즘으로 푸는 것보다, 알고리즘이 더 효율적일 수도 있음에 유의한다.
전체 40%의 입력데이터에 있어서, 1<=N<=15를 만족한다.
출력
당신이 얻을 수 있는 최대의 점수를 출력한다. 정답은 항상 100의 배수임을 유의하라.
예제
5 100
10 50 100 150 150
20 200 20 20 20
400
출처
ohjtgood
로그인해야 코드를 작성할 수 있어요.