Problem J
Blacksmith Training

Photo by Fir0002

Zapray is playing the game World of Warcraft Classic. In the game he needs to train his blacksmith skill from level $0$ to level $300$. He will improve his blacksmith skill by crafting items described in blacksmith plans.

Blacksmith plans are taught by trainers around the world. There are $n$ plans available for Zapray to learn. Plan $i$ is taught at a price of $p_ i$ gold, and has an entry level $e_ i$ and a master level $m_ i$. Zapray can only learn the plan if his blacksmith skill level is at least $e_ i$. After learning the plan, Zapray can craft the item described in the plan, such as a piece of armor or a weapon. He may craft as many items as he wishes using plan $i$, but he must pay $d_ i$ gold for the materials of each item to craft. Zapray’s blacksmith skill will level up by one after he crafts an item using any blacksmith plan. However, once Zapray’s skill level reaches the master level $m_ i$, plan $i$ becomes too elementary for Zapray and crafting an item using plan $i$ can no longer increase his skill level.

Zapray wants to know the minimum amount of gold he needs to spend to train his blacksmith skill to level $300$.

Input

The input starts with a single integer $n$ ($1 \leq n \leq 80$) on the first line. The $i$th of the following $n$ lines consists of four integers $e_ i$, $m_ i$, $p_ i$, $d_ i$ ($0 \leq e_ i < m_ i \leq 300, 0 \leq p_ i, d_ i \leq 10^6$) that describe the $i$th blacksmith plan. It is guaranteed that Zapray’s blacksmith skill can reach level $300$ from level $0$ with the given set of plans.

Output

Output the minimum amount of gold Zapray needs to spend.

Note

World of Warcraft Classic is developed and released by Blizzard Entertainment. Blizzard Entertainment does not endorse and has no involvement with the ProgNova contest.

4
0 100 1000 100
100 150 2000 50
150 250 3000 20
150 300 1000 60

24500