페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8278

나는 기말고사형 인간이야 1s 1024MB

문제

중간고사를 시원하게 망친 찬우는 오늘부터 1분도 쉬지 않고 기말고사 공부에 매진하기로 다짐했다.

기말고사는 정확히 24\times N시간 이후에 시작되며, 쉬는 시간 없이 하루에 모든 과목의 시험을 보기 때문에 찬우는 24\times N시간동안 공부할 수 있다. 기말고사를 보는 과목은 총 M개로, 시험 시간이 빠른 과목부터 각각 1부터 M까지의 번호가 매겨져 있다. 모든 과목의 최저점은 0점, 최고점은 100점이다.

찬우는 공부를 하나도 하지 않아도 i번 과목에서 a_{i} 점을 받을 수 있으며, i번 과목을 정확히 한 시간 공부할 때마다 그 과목의 성적을 b_{i}점 올릴 수 있다. 하지만 i번 과목을 30분 공부한다고 \frac{b_{i}}{2}점이 오르지는 않으며, 아무리 공부하더라도 한 과목에서 최고점인

100점이 넘는 점수를 받을 수는 없다.

모든 과목의 점수의 합이 찬우의 최종 성적이 된다. 높은 성적을 받기 위한 최적의 전략으로 공부할 때, 찬우가 받을 수 있는 최종 성적의 최댓값을 출력하는 프로그램을 작성하시오.


입력

첫째 줄에 정수 N, M이 공백으로 구분되어 주어진다.

둘째 줄에는 정수 a_{1}, a_{2}, ..., a_{M}이 공백으로 구분되어 주어진다.

셋째 줄에는 정수 b_{1}, b_{2}, ..., b_{M}이 공백으로 구분되어 주어진다.

  • 1 \leq N, M \leq 200\,000 

  • 1 \leq a_{i}, b_{i} \leq 100 


출력

첫째 줄에 찬우가 받을 수 있는 최종 성적의 최댓값을 출력한다.


예제 #1

1 2
50 60
4 3
194

24시간 동안 두 과목을 모두 12시간씩 공부하면 1번 과목은 98점, 2번 과목은 96점을 받게 된다.

이때 찬우의 최종 성적은 194점이 되며, 과목별 공부시간을 어떻게 조절해도 194점보다 높은 성적을 받을 수는 없다.


예제 #2

8 7
30 15 70 50 40 40 50
2 2 1 3 1 2 1
627

192시간 동안 1번 과목을 35시간, 2번 과목을 43시간, 3번 과목을 30시간, 4번 과목을 17시간, 5번 과목을 37시간, 6번 과목을 30시간동안 공부하면 1, 2, 3, 4, 6번 과목은 100점, 5번 과목은 77점, 7번 과목은 50점을 받게 된다. 이때 찬우의 최종 점수는 627점이 되며, 과목별 공부시간을 어떻게 조절해도 627점보다 높은 성적을 받을 수는 없다.


예제 #3

1 1
100
1
100


출처

선린 가을맞이 알고리즘 챌린지 Beginner Division D번
로그인해야 코드를 작성할 수 있어요.