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

#5683

천사소년 서준이 1초 256MB

문제

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

천사소년 서준이는 의적이다. 서준이는 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)가 공백으로 구분되어 입력된다.

<부분문제>

  1. n<=10 (25점)

  2. c_j<=10 (35점)

  3. 추가 조건 없음 (40점)


출력

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


예제1

입력
4 3
180
160
170
190
2 100
3 120
4 250
출력
480

예제2

입력
2 2
1000
2000
1 6666
1 7777
출력
0

출처

JOI 2014 2번

역링크 공식 문제집만