Rabbit Plays Games!

Time limit1sMemory limit512 MB

Summary

In a turn-based battle where characters act by agility, pick which enemy the protagonist attacks each turn to survive and minimize total damage taken.

Level: Medium7 of 10
Topics: Greedy, Sorting, Simulation, Binary search
Solved: No attempts yet

Problem

A rabbit is playing a role-playing game. Right before entering the castle, enemies were lying in ambush!

The rabbit's single protagonist fights n enemies. Each character has four stats: health hi, attack ai, defense di, and agility si. i = 0 holds the protagonist's information, and 1 ≤ i ≤ n holds each enemy's information.

Combat is turn-based. In each turn, the surviving characters attack in order of decreasing agility. Enemies always attack the protagonist. The protagonist attacks one enemy, and can choose which enemy to attack each turn. When a character with attack a attacks a character with defense d, the damage dealt is max{a − d, 0}. A character whose total damage received reaches its health immediately becomes unable to fight. Combat ends when the protagonist becomes unable to fight or when all enemies become unable to fight.

Input

1 ≤ n ≤ 40 000
1 ≤ hi, ai, di, si ≤ 1 000 000 000 (integers)
All si are distinct.

Output

If the protagonist is guaranteed to become unable to fight, output −1. Otherwise, output the minimum total damage the protagonist receives on one line.

Examples2

Example 1
Input
```
2
10 3 1 2
2 4 1 3
2 2 1 1
```
Expected output
```
4
```
Example 2
Input
```
1
1 1 1 1
10000 10000 10000 10000
```
Expected output
```
-1
```