Bookshelf Bottleneck

Interview

Time limit3sMemory limit1024 MB

Summary

Each book can be rotated so one side is at most H tall, and the task is to find the minimum total shelf width needed to place all n books in a line.

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

Problem

Brianna is a bookworm. At home she has a big bookshelf that holds all her favourite books, from detective novels and science-fiction novels to biographies.

Recently Brianna added $n$ graphic novels to her collection. The new books now lie around the room in huge stacks on the floor. Meanwhile, one of the shelf boards has collected dust and random household utensils that do not belong there. The loose books have become too much to bear, so she has decided to put them on this shelf board. To do so, she first has to make room on it.

Figure B.1: Visualization of the third input.

Brianna wants to arrange the books in a single horizontal line without stacking them on top of each other. The shelf is wide enough to hold all the books, but clearing room on it takes time. So she wants to minimize the width of the part of the shelf that she needs to clear.

Each book is a cuboid with side lengths $l$ , $w$ , and $h$ . The space above the shelf board is limited by the next shelf board, so a book can stand upright only if its vertical side length is at most the distance $H$ between the two shelf boards. Brianna may rotate each book in three-dimensional space as she wants. The shelf is guaranteed to be deep enough that no book falls off, whatever its orientation. However, every book must stand properly on the shelf board, touching it along an entire face and not just along an edge.

What is the minimum width of shelf that the books need?

Input

The input consists of:

One line with two integers $n$ and $H$ ( $1\leq n\leq 10^5$ , $1\leq H \leq 10^9$ ), the number of books and the height of the shelf.

$n$ lines, each containing three integers $l$ , $w$ , $h$ ( $1\leq l,w,h \leq 10^9$ ), the dimensions of one book.

Output

Output the minimum width of shelf the books need, or impossible if it is impossible to place the books on the shelf.

Examples4

Example 1
Input
```
1 3
10 2 5
```
Expected output
```
5
```
Example 2
Input
```
1 3
10 4 5
```
Expected output
```
impossible
```
Example 3
Input
```
2 10
10 2 10
2 3 4
```
Expected output
```
4
```

Example 4

Input

3 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

Expected output

3000000000