Caterpillar Walk

Interview

Time limit1sMemory limit1024 MB

Summary

Given non-overlapping buildings on the x-axis, find the total distance Lulu crawls along roofs and walls from x=0 to x=100.

Level: Easy3 of 10
Topics: Implementation, Array
Solved: No attempts yet

Problem

Consider a city where each building is a rectangle with its base on the positive x-axis, its two walls parallel to the positive y-axis, and its roof parallel to the x-axis. Two buildings may touch each other, so they can stand right next to each other. However, no two buildings may share any area, meaning they do not intersect or overlap.

Lulu, our beloved caterpillar, lives at $(0,0)$ and works at $(100,0)$ . Every morning, Lulu crawls from home to the office. Without any buildings, the trip is a distance of 100. The buildings force Lulu to crawl up and down the walls, which adds to the distance. Lulu starts at home and ends at the office, and is always crawling on the x-axis, up the side of a wall, across the top of a building, or down the side of a wall.

Given the description of all the buildings, compute the total distance Lulu travels.

Input

The first line contains an integer $n$ ( $1 \le n \le 50$ ), the number of buildings. Each of the next $n$ lines describes one building with three integers: $s$ ( $1 \le s \le 98$ ), $w$ ( $1 \le w \le 98$ ), and $h$ ( $1 \le h \le 100$ ). Here $s$ is the x-coordinate of the lower-left corner, $w$ is the width, and $h$ is the height. It is guaranteed that $s + w \le 99$ , so no building extends beyond $(99,0)$ .

Output

Print the total distance Lulu travels.

Hint

The picture below shows the last input example.

Examples5

Example 1
Input
```
2
40 3 7
60 10 12
```
Expected output
```
138
```
Example 2
Input
```
2
43 10 12
40 3 7
```
Expected output
```
124
```
Example 3
Input
```
3
40 3 7
43 10 12
53 20 8
```
Expected output
```
124
```
Example 4
Input
```
3
70 20 8
40 3 7
43 10 12
```
Expected output
```
140
```
Example 5
Input
```
4
12 2 10
14 4 20
18 6 15
24 8 25
```
Expected output
```
160
```