Степан, який працює в піцерії, готує смачну сирну піцу для персоналу. Перед ним \(N\) видів сиру. Смачність сиру \(i\)-го сорту – \(А_і\) за грам, і \(B_i\) грам цього сиру є в наявності. Смачність піци буде цілковитою смачністю сиру, який він покладе на піцу. Однак використання занадто великої кількості сиру розлютило б його боса, тому піца може мати щонайбільше \(W\) грамів сиру. За цієї умови знайдіть максимально можливу смачність піци.

Формат вхідних даних

Перший рядок містить ціле число \(N, W\) (\(1 \le N \le 3 \times 10^5\), \(1 \le W \le 3 \times 10^*\) )

Наступні  \(N\) рядків містять цілі числа \(A_i, B_i\) (\(1 \le A_i \le 10^9\), \(1 \le B_i \le 1000\))

Числа у рядках розділяються пропуском.

Формат вихідних даних

У вихідний потік виведіть шукану смачність піци.

Примітка

До прикладу 1:

Оптимальний вибір – 1 грам сиру першого сорту, 2 грами другого і 2 грами третього. Піца матиме смак 15.

Приклад вхідних даних

3 5
3 1
4 2
2 3

Приклад вихідних даних

15

Приклад вхідних даних

4 100
6 2
1 5
3 9
8 7

Приклад вихідних даних

100

Приклад вхідних даних

10 3141
314944731 649
140276783 228
578012421 809
878510647 519
925326537 943
337666726 611
879137070 306
87808915 39
756059990 244
228622672 291

Приклад вихідних даних

2357689932073