시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB207987651.701%

문제

중간고사를 시원하게 망친 찬우는 오늘부터 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

예제 출력 1

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

예제 출력 2

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

예제 출력 3

100