Bookshelf Bottleneck

시간 제한3초메모리 제한1024 MB

요약

n개의 직육면체와 선반 높이 H가 주어질 때, 각 책을 높이에 맞게 회전시켜 바닥에 놓았을 때 필요한 최소 너비를 구한다.

난이도: 보통10점 중 5점
유형: 그리디, 수학, 정렬, 구현
정답자: 아직 제출이 없습니다

문제

Brianna is a bookworm. At home, she has a big bookshelf with all her favourite books. She has a large collection ranging from detective novels and science-fiction novels to biographies.

Recently, Brianna has expanded her collection with $n$ graphic novels. However, the new books currently lie around everywhere and form huge stacks on the floor. In the meantime, one of the shelf boards has collected dust and random household utensils that do not belong there. The new books just lying around have become too much to bear, and Brianna finally decided to put them on this shelf board. To do so, she first has to make room on it.

Figure B.1: Visualization of Sample Input 3.

Brianna wants to arrange the books in a single horizontal line without stacking multiple books on top of each other. While the shelf is wide enough to hold all books without problems, it takes time to make room on the shelf. Therefore, Brianna wants to minimize the width of the part of the shelf that she needs to clear.

Each book can be described as a cuboid with three side lengths $l$ , $w$ , and $h$ . Since the room above the shelf board is limited by the next shelf board above it, she can only fit a book vertically 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. It is guaranteed that the shelf is deep enough so that the books will not fall off, no matter the orientation. However, all books must stand properly on the shelf board, meaning that every book touches the shelf board along an entire face and not just by an edge.

What is the minimum width of shelf Brianna's books need?

입력

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, respectively.
$n$ lines, each containing three integers $l$ , $w$ , $h$ ( $1\leq l,w,h \leq 10^9$ ), the dimensions of the books.

출력

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

예제4

예제 1
입력
```
1 3
10 2 5
```
예상 출력
```
5
```
예제 2
입력
```
1 3
10 4 5
```
예상 출력
```
impossible
```
예제 3
입력
```
2 10
10 2 10
2 3 4
```
예상 출력
```
4
```

예제 4

입력

3 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000
1000000000 1000000000 1000000000

예상 출력

3000000000