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>| {
        // todo!("Remove clone!");

        let sum_of_generators = solution
            .iter()
            .map(|&index| data.generators[index].clone())
            .collect::<Vec<Generator>>();

        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);
                    }
                }
                None => best_combination = Some(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 {
        onsolution(&solution);

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