27164번 - 도미니언

문제

《도미니언》의 확장판 《Dominion: Last Turn》은 매 턴마다 카드를 구매하여 덱을 구성하고 최후의 턴에 승점을 계산하는 게임입니다.

《도미니언》은 두 종류의 카드를 사용합니다. 하나는 행동 카드이며, 다른 하나는 승점 카드입니다. 행동 카드는 정수 $A$와 $B$가 새겨져 있으며, $A$번의 행동 횟수를 추가해 주고, $B$개의 카드를 뽑게 해 줍니다. 승점 카드에는 정수 $P$가 새겨져 있으며, 승점을 뜻합니다.

이러한 카드들을 한 턴에 하나씩 구매하여 덱을 만들고, 마지막 턴에는 아래와 같은 과정으로 승점을 계산합니다

1. 플레이어는 덱을 자신이 원하는 순서대로 정렬합니다.
2. 플레이어는 덱에서 카드를 1ドル$장 뽑고 1ドル$번의 행동 기회를 가지는 것으로 시작합니다.
3. 플레이어는 행동 횟수가 1ドル$ 이상일 때 행동 기회를 1ドル$ 소모하여 행동 카드를 사용할 수 있습니다. 이 경우 플레이어는 $A$번의 행동을 추가로 할 수 있으며, $B$장의 카드를 덱에서 뽑습니다. 단, 덱에 남아있는 카드가 $B$장보다 적을 경우 모두 뽑습니다.
4. 더 이상 행동을 할 수 없거나 플레이어가 종료를 선언하면 손에 들고 있는 승점 카드에 새겨진 승점의 값의 합계가 최종 승점이 됩니다.

유토는 이제 마지막으로 한 번의 구매 후 승점을 계산해야 합니다. 현재 유토의 덱과 구매할 수 있는 카드의 목록이 주어졌을 때 유토가 한 장을 덱에 추가한 후 얻을 수 있는 최대 승점을 알려주세요.

입력

입력의 첫째 줄에는 현재 덱에 있는 카드의 수 $N$과 덱에 추가할 수 있는 카드의 종류 개수인 $M$이 공백으로 구분되어 주어집니다.

이후 $N$개의 줄에 걸쳐 덱에 있는 카드의 정보가 주어집니다.

이후 $M$개의 줄에 걸쳐 구매할 수 있는 카드의 정보가 주어집니다.

카드에 대한 정보는 카드가 행동 카드라면 Act $A$ $B$ 의 형태로 주어지며, 승점 카드라면 Point $P$ 의 형태로 주어집니다.

출력

유토가 얻을 수 있는 최대 승점을 출력해주세요.

제한

• 1ドル \le N, M \le 1,000円,000円$
• 0ドル \le A, B \le 1,000円,000円$
• $A + B > 0$
• 0ドル \le P \le 1,000円$

힌트