use std::cmp::min;
use std::fs::File;
use std::io::{BufRead, BufReader, Write};

const MAX_N: usize = 5005;

pub fn main() {
    let file = File::open("energii.in").expect("Failed to open file!");
    let reader = BufReader::new(file);
    let mut lines = reader.lines();

    let read_line_error = "Failed to read line";
    let parse_int_error = "Failed to parse line as i64";

    let num_generators: usize = lines
        .next()
        .unwrap()
        .expect(read_line_error)
        .parse()
        .expect(parse_int_error);

    let target_energy: usize = lines
        .next()
        .unwrap()
        .expect(read_line_error)
        .parse()
        .expect(parse_int_error);

    let mut cost_array: [usize; MAX_N] = [0xffffffff - 10001; MAX_N];

    lines.take(num_generators).for_each(|line| {
        let parts: Vec<usize> = line
            .unwrap()
            .split_whitespace()
            .map(|s| s.parse().expect("Failed to parse number"))
            .collect();
        let energy_generated = parts[0];
        let cost_to_start = parts[1];

        for j in (0..target_energy + 1).rev() {
            if j > energy_generated {
                cost_array[j] = min(
                    cost_array[j],
                    cost_array[(j - energy_generated)] + cost_to_start,
                );
            } else {
                cost_array[j] = min(cost_array[j], cost_to_start)
            }
        }
    });

    let mut file = File::create("energii.out").expect("Failed to create output file");

    if cost_array[target_energy] == 0xffffffff - 10001 {
        file.write_all("-1".as_bytes())
            .expect("Failed to write to output file");
    } else {
        writeln!(&mut file, "{}", cost_array[target_energy]).unwrap();
    }
}