시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 4 3 75.000%

문제

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 ≤ 106, 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 ai, bi (2 ≤ ai, bi ≤ 104), 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ś.

예제 입력 1

2 2
2 5
3 6

예제 출력 1

18