토끼가 게임을 한다!

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

요약

민첩성 순서로 행동하는 턴제 전투에서 주인공이 매 턴 공격할 적을 골라 생존하면서 받는 총 피해를 최소화한다.

난이도: 보통10점 중 7점
유형: 그리디, 정렬, 시뮬레이션, 이분 탐색
정답자: 아직 제출이 없습니다

문제

토끼가 어떤 롤플레잉 게임을 하고 있다. 성에 들어가기 직전에 적들이 매복해 있었다!

토끼가 조작하는 주인공 1명과 n명의 적이 싸운다. 각 캐릭터에는 네 가지 능력치, 체력 hi, 공격력 ai, 방어력 di, 민첩 si가 정해져 있다. i = 0은 주인공의 정보, 1 ≤ i ≤ n은 각 적의 정보를 나타낸다.

전투는 턴제이다. 각 턴마다 살아 있는 캐릭터가 민첩이 높은 순서대로 공격한다. 적은 반드시 주인공을 공격한다. 주인공은 적 1명을 공격하는데, 어느 적을 공격할지는 매 턴마다 주인공이 고를 수 있다. 공격력 a인 캐릭터가 방어력 d인 캐릭터를 공격할 때 max{a − d, 0}의 피해를 입힌다. 받은 피해의 합이 체력 이상이 된 캐릭터는 즉시 전투 불능이 된다. 주인공이 전투 불능이 되거나 적이 모두 전투 불능이 되면 전투가 끝난다.

입력

1 ≤ n ≤ 40 000
1 ≤ hi, ai, di, si ≤ 1 000 000 000 (정수)
si는 모두 다르다.

출력

주인공이 반드시 전투 불능이 되는 경우 −1을 출력한다. 그렇지 않은 경우 주인공이 받는 피해의 합의 최솟값을 한 줄에 출력한다.

예제2

예제 1
입력
```
2
10 3 1 2
2 4 1 3
2 2 1 1
```
예상 출력
```
4
```
예제 2
입력
```
1
1 1 1 1
10000 10000 10000 10000
```
예상 출력
```
-1
```