Submission #67755123

---

Source Code Expand

use std::cmp::max;
use proconio::*;

pub fn main() {
  input! {
    mut n: usize,
    m: usize,
    a: [(usize, usize); m]
  }
  let mut best = vec![0; 301];
  for (x, y) in a {
    best[x] = max(best[x], y);
  }
  let mut dp = vec![0; 2000001];
  for i in 0..dp.len() {
    dp[i] = i;
    for (x, y) in best.iter().enumerate() {
      if i >= x {
        dp[i] = max(dp[i], x + dp[i - x + y]);
      }
    }
  }
  let mut bestx = 0;
  let mut besty = 0;
  for (x, &y) in best.iter().enumerate() {
    if y != 0 && (bestx == 0 || bestx * (x - y) <= x * (bestx - besty)) {
      bestx = x;
      besty = y;
    }
  }
  let mut add = 0;
  if n >= dp.len() {
    let c = 1 + (n - dp.len()) / (bestx - besty);
    add = bestx * c;
    n -= c * (bestx - besty);
  }
  println!("{}", dp[n] + add);
}

Submission Info

Judge Result