Placeholder

#5683

천사소년 서준이 1초 256MB

문제

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

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


입력

첫 줄에 m(1<=m<=10000)m(1<=m<=10000)n(1<=n<=500)n(1<=n<=500)이 공백으로 구분되어 입력된다.

다음 mm줄에 ii번째 보석의 가치 pi(1<=pi<=10000)p_i(1<=p_i<=10000)가 입력된다.

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


<부분문제>

  1. n<=10n<=10 (25점)

  2. cj<=10c_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번


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.