영화광

Byteasar는 열렬한 영화광이라, 그가 가장 좋아하는 스튜디오 영화관에서 여름 영화 마라톤이 열린다는 소식을 듣고 기뻐했다. 여름의 n일 동안 매일 m편의 영화 중 한 편이 상영된다. 마라톤 패스를 사면 원하는 만큼 영화를 볼 수 있지만, 하루도 빠뜨리지 않고 연속으로 봐야 한다. 하루를 건너뛰면 패스가 무효가 된다. 다만 첫날은 자유롭게 정할 수 있다.

Byteasar는 인터넷 리뷰를 보고 m편의 영화 각각에 점수를 매겼다. 이제 그는 여름 패스로 볼 영화의 점수 합을 최대화하려 한다. 문제를 어렵게 만드는 것은 Byteasar가 같은 영화를 두 번 보는 것을 견디지 못한다는 점이다. 같은 영화를 다시 보면 지루할 뿐 아니라, 그 영화에 대해 품고 있던 좋은 기억도 모두 사라진다. 따라서 그는 정확히 한 번만 보게 될 영화들의 점수 합을 최대화하려 한다.

첫 줄에 정수 n과 m(1 ≤ m ≤ n ≤ 1 000 000)이 공백 하나를 사이에 두고 주어진다. n은 여름 영화 마라톤의 길이, m은 영화의 수이다. 표기의 편의를 위해 영화에 1부터 m까지 번호를 붙인다.

둘째 줄에 n개의 정수 f1, f2, ..., fn(1 ≤ fi ≤ m)이 공백 하나를 사이에 두고 주어진다. fi는 마라톤 i일차에 상영되는 영화의 번호이다. 셋째 줄에 m개의 정수 w1, w2, ..., wm(1 ≤ wj ≤ 1 000 000)이 공백 하나를 사이에 두고 주어진다. wj는 j번 영화의 점수이다. 마라톤 동안 m편 중 일부는 전혀 상영되지 않을 수도 있다.

전체 점수의 70%에 해당하는 테스트 묶음에서는 n ≤ 100 000이고, 그중 20%에 해당하는 부분 묶음에서는 n ≤ 8000이다.

첫 줄이자 유일한 줄에, Byteasar가 여름 영화 마라톤 패스로 정확히 한 번만 볼 수 있는 영화들의 점수 합의 최댓값을 나타내는 정수 하나를 출력한다.

Byteasar는 마라톤 둘째 날부터 패스를 사용해 영화 6편을 볼 수 있다. 이때 2번, 3번, 4번 영화를 정확히 한 번씩 보게 된다.