---

import sys
from collections import deque

def solve():
    # Использование быстрого ввода данных
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    n = int(input_data[0])
    s_target = int(input_data[1])
    
    # Инициализация: S + 1 заменяет бесконечность
    inf = s_target + 1
    dp = [inf] * (s_target + 1)
    dp[0] = 0
    
    ptr = 2
    for _ in range(n):
        v = int(input_data[ptr])
        c = int(input_data[ptr+1])
        ptr += 2
        
        if v > s_target:
            continue
            
        # Кейс неограниченного рюкзака (если монет больше, чем может вместить сумма)
        if v * c >= s_target:
            for i in range(v, s_target + 1):
                new_val = dp[i-v] + 1
                if new_val < dp[i]:
                    dp[i] = new_val
            continue

        # Оптимизация скользящим окном для каждого остатка r
        for r in range(v):
            dq = deque()
            # Копируем текущий срез DP для этого остатка, чтобы использовать старые значения
            # Это необходимо для соблюдения лимита монет c
            current_remainder_vals = [dp[i] for i in range(r, s_target + 1, v)]
            
            for p, old_val in enumerate(current_remainder_vals):
                val_to_store = old_val - p
                
                # Поддержание минимума в окне
                while dq and dq[-1][0] >= val_to_store:
                    dq.pop()
                dq.append((val_to_store, p))
                
                # Удаление элементов, вышедших за пределы лимита c
                if dq[0][1] < p - c:
                    dq.popleft()
                
                # Обновление основного массива DP
                dp[r + p * v] = dq[0][0] + p

    result = dp[s_target]
    print(result if result <= s_target else -1)

if __name__ == "__main__":
    solve()