Informatica Online Judge

  만두 [0980 / 03D4]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 20   Total Tried : 134


The Champion of this Problem (C++) : gs19043 - 0ms / 1002byte
My Best Submission (C++) : N/A

[JOI 2014]

Background

GSHS는 음식을 만드는 회사이다. 이번에 GSHS사에서는 매우 특별한 맛을 내는 만두를 만들어서 판매하기로 했다.

GSHS사에서 M개의 종류의 만두를 1개씩 만들었다. 만들어진 M개의 만두는 모두 같은 크기지만, 맛이 모두 다르므로, 가격은 서로 다를 수 있다.

i번째 만두의 가격은 Pi원이다.

그런데 경곽이가 GSHS사에서 만든 만두를 담을 수 있는 상자를 만들고 있다.

경곽이가 만드는 상자는 모두 N개로 j번째 상자는 최대 Cj개의 만두를 담을 수 있는 크기이며, 상자의 가격은 Ej원이다.

이들 N개의 상자들 중 몇 개(0이상 N이하)를 GSHS사에서 만두를 판매하기 위하여 샀으며, GSHS사는 만두를 그 상자들 속에 넣어서 세트로 판매하도록 하고 있다.

각 만두 세트의 가격은 상자에 담긴 각 만두 가격의 합이다.

세트로 제작한 모든 제품을 판다고 가정할 경우, GSHS사가 얻는 이득의 최대값은 얼마나 될까?

여기서 이익이란 판매한 만두 세트의 가격의 합계로부터 경곽이에게 구입한 상자의 가격을 뺀 값을 의미한다.

또한, 상자에 넣지 않아 세트화 되지 않고 남은 만두는 GSHS사의 직원들이 맛있게 먹기 때문에 손해로 보지는 않는다.

Input

첫 번째 줄에 만두의 수 M과 상자의 수 N이 공백으로 구분되어 입력된다.
두 번째 줄부터 M줄에 걸쳐서 각 만두의 가격 Pi가 입력된다.
그 다음 줄부터 N줄에 걸쳐서 상자의 크기 Ci와 각 상자의 가격 Ei가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= M <= 10,000
1 <= N <= 500
1 <= Pi, Cj, Ej <= 10,000
( 1 <= i <= M, 1 <= j <= N )

[부분문제]
sub-task #1 : N <= 10 을 만족한다. (33.33%)
sub-task #2 : Cj <= 10을 만족한다. (33.33%)
sub-task #3 : 정의역의 조건과 같다. (33.33%)

Output

얻을 수 있는 최대 이득을 출력한다.

IO Example

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

출력1
480

[해설] 상자 1, 2을 구입하고, 1번 상자에 만두 2개, 2번 상자에 만두 2개를 넣으면, 총 판매금액은 700원이고 상자의 가격이 220원이므로 총 이득은 700-220 = 480원이며 이보다 더 많은 이득을 볼 수 있는 경우는 없다.

입력2
2 2
1000
2000
1 6666
1 7777

출력2
0

[해설] 이 경우에는 상자를 안사고 만두를 하나도 안파는 것이 가장 이득이다. 상자를 사서 이득을 볼 수 있는 경우가 없기 때문이다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]