use std::fs::File;
use std::io::Write;
use std::io::{BufRead, BufReader};
use std::path::Path;

const INPUT_FILE: &str = "./energii.in";
const OUTPUT_FILE: &str = "./energii.out";

// #[derive(Debug)]
struct FileData {
    m: i64,
    n: i64,
    generators: Vec<Generator>,
}

// #[derive(Debug)]
struct Generator {
    consumption: i64,
    production: i64,
}

impl FileData {
    fn new<P>(filename: P) -> Self
    where
        P: AsRef<Path>,
    {
        let file = File::open(filename).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 n: i64 = lines
            .next()
            .unwrap()
            .expect(read_line_error)
            .parse()
            .expect(parse_int_error);

        let m: i64 = lines
            .next()
            .unwrap()
            .expect(read_line_error)
            .parse()
            .expect(parse_int_error);

        let generators: Vec<Generator> = lines
            .take(n as usize)
            .map(|line| {
                let parts: Vec<i64> = line
                    .unwrap()
                    .split_whitespace()
                    .map(|s| s.parse().expect("Failed to parse number"))
                    .collect();
                return Generator {
                    consumption: parts[0],
                    production: parts[1],
                };
            })
            .collect();

        return Self { m, n, generators };
    }
}

pub fn solve_energii() -> i64 {
    let data = FileData::new(INPUT_FILE);

    let mut upper_mask: usize = 1;

    // you can do this with pow(2, k) - 1
    for _ in 0..(data.n - 1) {
        upper_mask = upper_mask << 1;
        upper_mask = upper_mask | 1;
    }

    let mut total_production = -1;
    let mut total_consumtion = -1;

    for i in 1..(upper_mask + 1) {
        let mut local_production = -1;
        let mut local_consumption = -1;

        for j in 0.. {
            if 1 << j > i {
                break;
            }
            let take_generator = i & j > 0;
            if take_generator {
                local_production += data.generators[j].production;
                local_consumption += data.generators[j].consumption;
            }
        }

        let is_good_enough = local_production + 2 > data.m;

        let is_better = total_consumtion == -1 || local_consumption < total_consumtion;

        if is_good_enough && is_better {
            total_production = local_production;
            total_consumtion = local_consumption;
        }
    }

    if total_production > -1 {
        total_production += 1;
        total_consumtion += 1;
    }

    return total_production;
    // println!("total_production = {total_production}; total_consumtion = {total_consumtion}");
}

pub fn main() {
    let solution = solve_energii();
    let mut output_buf = File::create(OUTPUT_FILE).expect("Failed to create the file");
    write!(&mut output_buf, "{}", solution).expect("Can not write to output file");
}