頁面無法載入？點擊這裡可能會修復。
Placeholder

#5683

천사소년 서준이 1s 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번

需要登入才能撰寫程式碼。