View problem - 만두 팔기 (JOI14_manju)

Language	Compilation command
C11	/usr/bin/gcc -DEVAL -std=gnu11 -O2 -pipe -static -s -o t2 t2.c -lm
C++20	/usr/bin/g++ -DEVAL -std=gnu++20 -O2 -pipe -static -s -o t2 t2.cpp
C++17	/usr/bin/g++ -DEVAL -std=gnu++17 -O2 -pipe -static -s -o t2 t2.cpp
Java	/usr/bin/javac -encoding UTF-8 t2.java /bin/sh -c echo "Main-Class: t2" > __manifest__.txt /bin/sh -c jar cfm t2.jar __manifest__.txt *.class
Pypy 3	/usr/bin/pypy3 -m compileall -b t2.py /bin/mv t2.pyc __main__.pyc /usr/bin/zip t2.pyz.zip __main__.pyc /bin/mv t2.pyz.zip t2.pyz

Time limit	Memory limit	# of submissions	# of submitted users	Solved #	Accepted user ratio
1000 ms	256 MiB	9	7	7	100.00%

상수는 만두를 만들어 생계를 유지하고 있습니다. 오늘 그는 $M$ 종류의 만두를 각각 한 개씩 만들었습니다. 이 만두들은 크기가 모두 같지만 맛이 다르기 때문에 가격이 가지각색입니다. $i$ ( $1 \le i \le M$ ) 번 만두의 가격은 $P_{i}$ 원입니다.

승현이는 상자들을 만들어 생계를 유지하고 있습니다. 그는 $N$ 종류의 포장 상자들을 판매하고 있으며, 이 중 $j$ ( $1 \le j \le N$ )번 상자에는 최대 $C_{j}$ 개의 만두를 넣을 수 있고 그 가격은 $E_{j}$ 원입니다.

상수는 승현이에게 한 종류당 최대 한 개의 상자를 구매하여 만두들을 이 상자에 나누어 넣어서 판매하고 한 상자를 한 세트라고 정의하기로 합니다. 각 만두 세트의 가격은 그 안에 들어있는 만두들의 가격의 합입니다. 상수는 모든 만두 세트들이 팔린다고 가정할 때 자신이 얻을 수 있는 최대 이익을 알고자 합니다. 이 때 이익은 판매한 만두 세트들의 가격의 합에서 승현이에게 구매한 상자들의 가격의 합을 뺀 값입니다. 상자에 넣지 않은 만두는 상수가 먹으면 되므로 이익에 영향을 주지 않습니다.

해야 할 일

상수가 만든 각 만두의 가격과 승현이가 판매하는 각 상자의 크기와 가격이 주어질 때, 상수가 얻을 수 있는 최대 이익을 구하는 프로그램을 작성하세요.

입력

첫 번째 줄에 상수가 만든 만두의 종류의 수 $M$ 과 승현이가 판매하는 상자의 종류의 수 $N$ 이 공백을 사이로 두고 주어집니다.
$M$ 개 줄이 주어집니다. 이 중 $i$ ( $1 \le i \le M$ )번째 줄에는 $i$ 번 만두의 가격 $P_{i}$ 가 주어집니다.
$N$ 개 줄이 주어집니다. 이 중 $j$ ( $1 \le j \le N$ )번째 줄에는 $i$ 번 상자에 넣을 수 있는 최대 만두의 수 $C_{j}$ 와 그 가격 $E_{j}$ 가 주어집니다.

출력 형식

첫 번째 줄에 상수가 얻을 수 있는 최대 이익을 출력합니다.

제약 조건

$1 \le M \le 10,000$
$1 \le N \le 500$
$1 \le P_{i} \le 10,000$ ( $1 \le i \le M$ )
$1 \le C_{j} \le 10,000$ ( $1 \le j \le N$ )
$1 \le E_{j} \le 10,000$ ( $1 \le j \le N$ )
모든 $P_{i}$ , $C_{j}$ , $E_{j}$ 는 정수입니다.

서브태스크

서브태스크 1 [25점]

$N \le 10$

서브태스크 2 [25점]

$C_{j} \le 10$ ( $1 \le j \le N$ )

서브태스크 3 [40점]

추가적인 제약 조건이 없습니다.

예제

입력

출력

상수는 승현이로부터 1번 상자 ( $100$ 원)와 2번 상자 ( $120$ 원)를 구매합니다. 상수는 1번 상자에 1번 만두와 2번 만두를 담아 $180 + 160 = 340$ 원에, 2번 상자에 3번 만두와 4번 만두를 담아 $170 + 190 = 360$ 원에 판매합니다. 이렇게 하면 이익은 $700 - 220 = 480$ 원입니다.

입력

출력

상자가 더 비싸니까 그냥 아무것도 안 하는 것이 최선입니다.

입력