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 {
    power_needed: i64,
    generators: Vec<Generator>,
}

#[derive(Debug, Clone)]
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[1],
                    production: parts[0],
                };
            })
            .collect();

        return Self {
            power_needed: m,
            generators,
        };
    }
}

pub fn solve_energii() -> i64 {
    let data = FileData::new(INPUT_FILE);
    let mut best_combination: Option<Generator> = None;

    let mut onsolution = |solution: &Vec<usize>| {
        let mut sum_generator = Generator {
            production: 0,
            consumption: 0,
        };

        for item in solution {
            sum_generator.consumption += data.generators[*item].consumption;
            sum_generator.production += data.generators[*item].production;
        }

        //        // todo!("Remove clone!");
        //
        //        let sum_of_generators = solution
        //            .iter()
        //            .map(|&index| data.generators[index].clone())
        //            .collect::<Vec<Generator>>();
        //
        //        // you can try this.
        //        let sum_generator = sum_of_generators.iter().fold(
        //            Generator {
        //                production: 0,
        //                consumption: 0,
        //            },
        //            |acc, item| Generator {
        //                production: acc.production + item.production,
        //                consumption: acc.consumption + item.consumption,
        //            },
        //        );

        if sum_generator.production >= data.power_needed {
            match &best_combination {
                Some(old_best) => {
                    if old_best.consumption > sum_generator.consumption {
                        best_combination = Some(sum_generator.clone());
                    }
                }
                None => best_combination = Some(sum_generator.clone()),
            }
        }
        return sum_generator;
    };

    // backtracking
    let start = 0;
    let end = data.generators.len() - 1; // data.generators.len() as i64;

    let mut solution = vec![];
    solution.push(start);

    while solution[0] != end {
        let last_g = onsolution(&solution);
        if last_g.consumption < data.power_needed {
            // this is unsafe but i dont care now.
            let last = solution.last().unwrap();
            if *last < end {
                solution.push(last + 1);
                continue;
            }
        }

        solution.pop();
        let prev = solution.pop().unwrap();
        solution.push(prev + 1);
    }
    onsolution(&solution);

    // println!("BEST {:?}", best_combination);
    return match &best_combination {
        Some(best) => best.consumption,
        None => -1,
    };
}

pub fn main() {
    let solution = solve_energii();
    // println!("{}", solution)

    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");
}