use std::fs;

trait PrintVec{
  fn write_solution(&self,file_path: &str);
}

impl PrintVec for Vec<i64>{
  fn write_solution(&self,file_path: &str){
    fs::write(file_path,self.iter().map(|num| num.to_string()).collect::<Vec<_>>().join(" "))
      .expect("Unable to write file");
  }
}

fn combinations(numbers: &[i64],k: i64,target_sum: i64) -> Option<Vec<i64>>{
  if numbers.last().unwrap()*k<target_sum{
    return None;
  }
  let mut combination=vec![];
  find_combination_with_repetition(numbers,k,target_sum,&mut combination)
}

fn find_combination_with_repetition(numbers: &[i64],k: i64,sum: i64,combination: &mut Vec<i64>) -> Option<Vec<i64>>{
  if sum==0 && k==0{
    return Some(combination.clone());
  }

  if sum<0 || k==0 || numbers.is_empty(){
    return None;
  }

  for (i,&number) in numbers.iter().enumerate(){
    combination.push(number);
    if let Some(result)=find_combination_with_repetition(&numbers[i..],k-1,sum-number,combination){
      return Some(result);
    }
    combination.pop();
  }

  None
}

fn main(){
  let content=
    fs::read_to_string("loto.in")
      .expect("Should have been able to read the file");
  let mut parts=content.split("\n");
  let sum: i64=
    parts
      .next().unwrap()
      .trim()
      .split_whitespace()
      .nth(1).unwrap()
      .parse().unwrap();
  let mut numbers: Vec<i64>=
    parts
      .next().unwrap()
      .trim()
      .split_whitespace()
      .collect::<Vec<&str>>()
      .iter()
      .map(|&x| x.parse::<i64>().unwrap())
      .collect::<Vec<i64>>();
  numbers.sort_unstable();
  if let Some(combination)=combinations(&numbers,6,sum){
    combination.write_solution("loto.out");
  }
  else{
    fs::write("loto.out","-1")
      .expect("Unable to write file");
  }
}