8722번 - Kratki 다국어

Jaś ma wiele czystych białych kartek papieru. Kartki mają różne wielkości. Jaś postanowił przerobić pewną białą kartkę na kartkę w kratkę – czyli chciałby dorysować pewną liczbę pionowych kresek i pewną liczbę poziomych kresek (równoległych do boków kartki), które podzielą kartkę na małe prostokąty.

Jaś musi jednak zachować odstęp d milimetrów pomiędzy kolejnymi liniami, zaś odległość linii od dowolnego boku musi wynosić co najmniej 1 milimetr. Jaś chciałby wybrać taką kartkę, którą będzie mógł podzielić na jak największą liczbę prostokątów (prostokąty utworzone pomiędzy pierwszą linią a bokiem kartki również liczymy). Ze wszystkich kartek, które będzie mógł podzielić na taką samą liczbę prostokątów, chciałby wybrać kartkę o największej powierzchni. Znajdź tą powierzchnię.

Pierwszy wiersz wejścia zawiera dwie liczby całkowite n, d (1 ≤ n ≤ 10⁶, 1 ≤ d ≤ 100), oznaczające odpowiednio liczbę białych kartek Jasia oraz minimalny odstęp pomiędzy liniami. Następnych n wierszy zawiera opisy kolejnych kartek papieru. Każdy z wierszy składa się z dwóch liczb całkowitych a_i, b_i (2 ≤ a_i, b_i ≤ 10⁴), oznaczających odpowiednio długość i szerokość i-tej kartki.

Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę oznaczającą powierzchnię kartki, którą powinien wybrać Jaś.