20902번 - Bookshelf Building 스페셜 저지다국어

Anna just came home from her favourite furniture store Ikey Yeah! where she bought a new bookshelf designed by her favourite artist Bill Lee. The shelf has a rectangular shape with a width of $x$ and a height of $y$. Included in the box of the shelf is one board that Anna may put horizontally inside the shelf. For this purpose the frame of the shelf already contains pre-drilled holes at heights $1,2,\ldots,y-1$. Anna may attach the board to the frame at any of these heights. She can also decide not to install it at all.

Anna owns $n$ books, which all have the same depth. The books' depth matches that of the shelf exactly. However, due to differences in the formats and the numbers of pages, her books may have different widths and heights. Anna does not want to flip her books or stack several of them on top of each other. Instead, she wants to store all of them in an upright fashion inside her bookshelf, such that the width and height of each book are aligned with the width and height of the bookshelf. Help Anna to find the perfect position for the board (or tell her not to use it at all) so that she can store all her books in her new bookshelf.

For this problem you may assume that the frame and the board of the shelf are infinitely thin.

The input consists of:

• One line with three integers $n$, $x$ and $y$, where 
  • $n$ ($1 \le n \le 10^4$) is the number of books that Anna owns;
  • $x$ ($1 \le x \le 10^4$) is the width of the bookshelf frame;
  • $y$ ($1 \le y \le 10^4$) is the height of the bookshelf frame.
• $n$ lines, the $i$th of which contains two integers $w_i$ and $h_i$, where
  • $w_i$ ($1 \le w_i \le 10^4$) is the width of the $i$th book;
  • $h_i$ ($1 \le h_i \le 10^4$) is the height of the $i$th book.

If there is no possibility to store Anna's books in the shelf, print out impossible. In case Anna decides not to install the board, output $-1$. Otherwise, output the height at which the board should be installed. If there are multiple possible heights, you may output any one of them.