#include <stdio.h>
#include <bits/stdc++.h>
//%lld
typedef long long ll;
using namespace std;
//Knapsack
int peso[1000];
int valor[1000];
int matriz[1000][1000];
int main(){
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    int s, n;
    while(scanf("%d", &n)==1){
        if(n==0)break;
        else{
            memset(matriz, 0, sizeof(matriz));
            memset(valor, 0, sizeof(valor));
            memset(peso, 0, sizeof(peso));
            scanf("%d", &s);
            for(int i = 0;i<n;i++){
                scanf("%d%d", &valor[i], &peso[i]);
            }
            for(int i = peso[0];i<=s;i++){
                matriz[0][i] = valor[0];
            }
            for(int i = 1;i<=n;i++){
                for(int j = 1;j<=s;j++){
                    if(peso[i]>j){
                        matriz[i][j] = matriz[i-1][j];
                    }else{
                        matriz[i][j] = max((valor[i]+matriz[i-1][j-peso[i]]), matriz[i-1][j]);
                    }
                }
            }
            int saida = 0;
            for(int i = 0;i<=s;i++){
                if(matriz[i][s]>saida)saida = matriz[i][s];
            }
            printf("%d min.\n", saida);
        }
    }
}