천사소년 서준이

주님, 오늘도 정의로운 도둑이 되는 걸 허락해 주세요!

천사소년 서준이는 의적이다. 서준이는 m개의 보석 중 일부를 훔쳐 얻은 수익으로 가난한 이들을 도우려 한다. 각각의 보석은 p_i원의 가치를 갖고 있다. 하지만, 서준이는 귀여운 천사소년이기 때문에 직접 보석을 들기에는 너무 보석이 크기 때문에 보석을 끌고 갈 캐리어를 사야 한다. 캐리어는 n개가 존재하며, 돈을 내고 구입할 수 있다. 각각의 캐리어는 c_i개의 보석을 담을 수 있으며, e_i원에 살 수 있다. 서준이가 최대 얼마나 벌 수 있을지 구해보자.

입력

첫 줄에

m(1<=m<=10000)

과

n(1<=n<=500)

이 공백으로 구분되어 입력된다.

다음 $m$ 줄에 $i$ 번째 보석의 가치 $p_i(1<=p_i<=10000)$ 가 입력된다.

다음 n줄에 $i$ 번째 캐리어의 크기 $c_i(1<=c_i<=10000)$ 와 가격 $e_i(1<=e_i<=10000)$ 가 공백으로 구분되어 입력된다.

<부분문제>

$n<=10$ (25점)
$c_j<=10$ (35점)
추가 조건 없음 (40점)

출력

서준이가 최대 얼마나 벌 수 있는지 출력한다.

예제1

예제2

출처

JOI 2014 2번

#5683

천사소년 서준이 1초 256MB

문제

입력

출력

예제1

예제2

출처

역링크 공식 문제집만

#5683 upload 432회 done 36회 how_to_reg 29명

천사소년 서준이 timer 1초 memory 256MB

문제 picture_in_picture_alt text_fields

입력

출력

예제1

예제2

출처

역링크 공식 문제집만

#5683

천사소년 서준이 1초 256MB

문제