У Farmer John заканчиваются запасы, и ему нужно купить $H$ $(1 \le H \le 50,000)$ фунтов сена для коров.

Он знает $N$ $(1 \le N \le 100)$ поставщиков сена, для удобства пронумерованных $1,\ldots,N$. Поставщик $i$ продаёт упаковки, содержащие $P_{i}$ $(1 \le P_{i} \le 5,000)$ фунтов сена, по цене $C_{i}$ $(1 \le C_{i} \le 5,000)$ долларов. У каждого поставщика неограниченное количество упаковок, и их необходимо покупать целиком.

Помогите FJ найти минимальную стоимость покупки не менее $H$ фунтов сена.

Входные данные

• Строка 1: два целых числа $N$ и $H$, разделённых пробелом.
• Строки $2,\ldots,N+1$: строка $i+1$ содержит два целых числа $P_{i}$ и $C_{i}$, разделённых пробелом.

Выходные данные

• Строка 1: одно целое число — минимальная сумма, которую FJ должен заплатить, чтобы получить не менее $H$ фунтов сена.

Примеры

Входные данные 1

2 15
3 2
5 3

Выходные данные 1

9

Примечание

FJ может купить три упаковки у второго поставщика за общую стоимость 9.

Автор задачи: Neal Wu, 2007