규칙적인 보스돌이

시간 제한1초메모리 제한1024 MB

요약

캐릭터 N개 중 M개를 골라 각각 하루 15분씩 보스를 사냥하게 하고, 처치한 보스의 메소 합이 최대가 되는 값을 구합니다.

난이도: 보통10점 중 7점
유형: 동적 계획법, 비트 연산, 완전 탐색
정답자: 아직 제출이 없습니다

문제

카오는 오랫동안 메이플스토리를 플레이하며 $N$ 개의 캐릭터를 육성하였다.

지속적인 스펙업을 위해 꾸준히 메소를 벌어야 할 필요성을 느낀 카오는, 지금까지 키워 온 캐릭터들을 활용해 메소를 벌기로 하였다. 여러 캐릭터로 보스를 효율적으로 잡기 위해, 하루에 캐릭터 한 명당 최대 $15$ 분씩, 최대 $M$ 개의 캐릭터만 보스를 잡기로 하였다.

캐릭터가 보스에게 데미지를 넣으면 보스의 체력이 데미지만큼 줄어들며, 보스의 체력이 $0$ 이하가 되면 보스를 잡게 된다. 데미지는 매초 계산되므로, $1$ 초 미만으로 가한 데미지는 보스에게 적용되지 않는다.

캐릭터는 주어진 $15$ 분 동안 매초 일정한 데미지를 넣을 수 있다. 보스를 잡은 뒤 다음 보스를 잡으러 이동하는 시간은 계산하지 않는다. 캐릭터마다 각 보스는 한 번씩만 처치할 수 있으며, 다른 캐릭터가 잡은 보스라도 현재 캐릭터가 잡지 않은 보스라면 잡을 수 있다. 보스를 잡는 도중에 캐릭터를 바꿀 수 없으며, 보스의 체력은 캐릭터 사이에서 공유되지 않으므로 한 캐릭터의 힘만으로 보스를 상대해야 한다.

보스의 체력과 보상 메소, 캐릭터의 데미지 정보가 주어질 때, 카오가 계획에 맞춰 하루에 보스를 잡아 얻을 수 있는 최대 메소를 구해 보자.

입력

첫 줄에는 보유한 캐릭터의 개수 $N$ , 하루에 사용할 캐릭터의 개수 $M$ , 보스의 가짓수 $K$ 가 공백으로 구분되어 주어진다. $(1 \le M \le N \le 49;$ $1 \le K \le 13)$

그다음 $N$ 줄에 걸쳐 캐릭터가 1초에 가하는 데미지 $D$ 가 주어진다. $(1 \le D \le 10^{11})$

그다음 $K$ 줄에 걸쳐 보스의 체력 $P$ 와 보스를 처치했을 때 드랍하는 메소 $Q$ 가 공백으로 구분되어 주어진다. $(1 \le P \le 2.66 \times 10^{11};$ $1 \le Q \le 1\,596\,506)$

입력으로 들어오는 모든 수는 정수임이 보장된다.

출력

카오가 계획에 맞추어 보스를 잡았을 때, 하루에 보스를 잡아 얻을 수 있는 최대 메소를 출력한다.

힌트

보스의 체력 $P$ 의 제한 $2.66 \times 10^{11}$ 와 드랍하는 메소 $Q$ 의 제한 $1\,596\,506$ 은 2023년 8월 10일 업데이트 이전의 가장 많은 체력(카오스 혼테일)과 결정의 가격(노멀 파풀라투스)을 가진 일간 보스의 정보이다.

예제2

예제 1
입력
```
3 2 3
1
2
3
900 30
1800 40
2700 50
```
예상 출력
```
110
```
예제 2
입력
```
2 2 3
10
20
8999 10
17999 100
1 1
```
예상 출력
```
110
```