Problem K
Water Slide Waste (Hard)

Water isn’t cheap, and it’s a shame to waste it. That’s why Wally, of Wally’s Water Park, wants your help figuring out how much water he will need to run all of the water slides in his park. Being the orderly guy Wally is, he’s designed his park such that each slide starts and ends at integer coordinates. All the water will enter the park from the inlet port located at coordinates (0, 0). Furthermore, any pipes connecting the slides must run along gridlines (i.e. they must run vertically or horizontally). Pipes can be used to connect any two key locations (the start of or end of a slide, or the inlet). Pipes may be bent but cannot be split or spliced (i.e. each pipe can only connect two key locations). Each slide will require a certain amount of water to run which must be supplied at the start of the slide. Water cannot go back up through a slide. Each pipe will also require 1 litre of water per each unit in length in order to prevent sudden bursts in pressure. Wally has given you permission to place the pipes however you wish as long as you follow his rule. You don’t have to worry about what will happen to the water afterwards as the entire park has been set up to drain the water to a treatment site that will recycle the water back through the initial inlet. What is the minimum amount of water needed to run all of the slides in Wally’s park?

Figure 1: Example optimal solutions for the first and second sample cases. The blue dots indicate the inlet port, the black dots indicate the start of a slide, the black lines indicate the slides, and the blue lines indicate the water.

Notes:

1. Slides can overlap, share starting and/or ending points and start or end at the same point as the inlet

2. The pipes run along the ground whereas the slides are all elevated, so there is no concern about the pipes interfering with the slides

3. You can also place multiple pipes along the same gridline without issue

Input

The first line of the input contains a single integer $n$ ($1\leq n\leq 100$) the number of slides in Wally’s park. The next $n$ lines each specify a slide. Each contain $5$ integers $x_s$, $y_s$, $x_e$, $y_e$, and $w$ ($0\leq x_s, y_s, x_e, y_e, w\leq 10^6$) the x and y coordinates of the start of the slide, the x and y coordinates of the end of the slide, and the amount of water (in litres) needed to run the slide.

Output

Output a single integer, the minimum amount of water (in litres) needed to run all of the slides in Wally’s park.

3
0 2 1 4 2
1 2 2 2 1
3 3 2 4 1

9

3
0 1 1 3 2
1 0 2 0 1
3 3 2 4 1

8