#include <cstdio>
#include <cstring>
#include <vector>
#include <utility>

int N, L, T;
std::vector<std::pair<int, int>> v;
bool m[101][101][101];

void read_input() {
  scanf("%d%d", &N, &L);
  v.push_back(std::make_pair(0, 0));
  for(int i = 0; i < N; ++i) {
    int A, B;
    scanf("%d%d", &A, &B);
    v.push_back(std::make_pair(A, B));
  }
}

void init_mem() {
  memset(m, 0, 101 * 101 * 101);
}

bool f() {
  for(int p = 0; p <= N; ++p) {
    m[0][0][p] = true;
  }

  for(int a = 1; a <= L; ++a) {
    for(int b = 1; b <= L; ++b) {
      for(int p = 1; p <= N; ++p) {
        int p_maxA = T / v[p].first;
        for(int i = 0; i <= p_maxA && m[a][b][p] != true; ++i) {
          int lit_A = i;
          int lit_B = (T - lit_A * v[p].first) / v[p].second;
          int new_a = std::max(0, a - lit_A);
          int new_b = std::max(0, b - lit_B);
          m[a][b][p] = m[a][b][p] || m[new_a][new_b][p - 1];
        }
      }
    }
  }

  return m[L][L][N];
}

void search(int li, int ls) {
  init_mem();
  if(li > ls) {
    T = li;
    return;
  }
  T = (li + ls) / 2;
  if(f()) {
    search(li, T - 1);
  } else {
    search(T + 1, ls);
  }
}

int main(int argc, char *argv[]) {
  freopen("lapte.in", "r", stdin);
  freopen("lapte.out", "w", stdout);

  read_input();
  search(1, 100);
  printf("%d\n", T);

  return 0;
}