Submit: 1 Solved: 1

[Submit] [Status] [Web Board] [Creator:]

The cows are building a roller coaster! They want your help to design as fun a roller coaster as possible, while keeping to the budget.

The roller coaster will be built on a long linear stretch of land of length *L* (1 ≤ *L* ≤ 1,000). The roller coaster comprises a collection of some of the *N* (1 ≤ *N* ≤ 10,000) different interchangable components. Each component *i* has a fixed length *W _{i}* (1 ≤

Each component *i* has a "fun rating" *F _{i}* (1 ≤

Line 1: Three space-separated integers: *L*, *N* and *B*.

Lines 2..*N*+1: Line *i*+1 contains four space-separated integers, respectively: *X _{i}*,

Line 1: A single integer that is the maximum fun value that a roller-coaster can have while staying within the budget and meeting all the other constraints. If it is not possible to build a roller-coaster within budget, output -1.

```
5 6 10
0 2 20 6
2 3 5 6
0 1 2 1
1 1 1 3
1 2 5 4
3 2 10 2
```

`17`

Taking the 3rd, 5th and 6th components gives a connected roller-coaster with fun value 17 and cost 7. Taking the first two components would give a more fun roller-coaster (25) but would be over budget.