import java.util.*;
public class exponentexchange_xiaowuc1 {
  public static void main(String[] args) throws Exception {
    Scanner sc = new Scanner(System.in);
    int b = sc.nextInt();
    int p = sc.nextInt();
    int[] vv = new int[p];
    for(int i = 0; i < p; i++) vv[i] = sc.nextInt();
    long[] nocarrydp = new long[1];
    long[] carrydp = new long[0];
    for(int qq = p-1; qq >= 0; qq--) {
      int currhave = vv[qq];
      long[] nnocarrydp = new long[nocarrydp.length + carrydp.length];
      int nnoidx = 0;
      long[] ncarrydp = new long[nocarrydp.length + carrydp.length];
      int ncarryidx = 0;
      for(int i = 0; i < nocarrydp.length; i++) {
        long k = (nocarrydp[i] >> 30);
        long v = (nocarrydp[i] & ((1L << 30) - 1));
        nnocarrydp[nnoidx++] = ((k+currhave) << 30) | v;
        ncarrydp[ncarryidx++] = (k << 30) | (v + (b-currhave));
      }
      currhave++;
      for(int i = 0; i < carrydp.length; i++) {
        long k = (carrydp[i] >> 30);
        long v = (carrydp[i] & ((1L << 30) - 1));
        if(currhave == b) {
          ncarrydp[ncarryidx++] = (k << 30) | v;
          continue;
        }
        nnocarrydp[nnoidx++] = ((k+currhave) << 30) | v;
        ncarrydp[ncarryidx++] = (k << 30) | (v + (b-currhave));
      }
      nocarrydp = trim(nnocarrydp, nnoidx);
      carrydp = trim(ncarrydp, ncarryidx);
    }
    int ret = Integer.MAX_VALUE;
    for(int i = 0; i < nocarrydp.length; i++) {
      long k = (nocarrydp[i] >> 30);
      long v = (nocarrydp[i] & ((1L << 30) - 1));
      ret = Math.min(ret, (int)(Math.max(k, v)));
    }
    for(int i = 0; i < carrydp.length; i++) {
      long k = (carrydp[i] >> 30);
      long v = (carrydp[i] & ((1L << 30) - 1));
      ret = Math.min(ret, (int)(Math.max(k, v)));
    }
    System.out.println(ret);
  }
  private static long[] trim(long[] dp, int sz) {
    Arrays.sort(dp, 0, sz);
    int curr = 0;
    for(int i = 0; i < sz; i++) {
      long k = dp[i] >> 30;
      long v = dp[i] & ((1L << 30) - 1);
      boolean good = true;
      while(curr > 0) {
        good = false;
        long pk = (dp[curr-1]) >> 30;
        long pv = (dp[curr-1]) & ((1L << 30) - 1);
        if(pk == k){
          if(pv >= v) curr--;
          else break;
        } 
        else {
          if(pk > k) throw new RuntimeException();
          if(pv > v) good = true;
          break;
        }
      }
      if(good) dp[curr++] = dp[i];
    }
    long[] ret = new long[curr];
    for(int i = 0; i < curr; i++) ret[i] = dp[i];
    return ret;
  }
  private static void ins(TreeMap<Integer, Integer> m, int k, int v) {
    if(m.size() > 0 && m.firstKey() <= k) {
      int cand = m.floorKey(k);
      if(m.get(cand) <= v) return;
    }
    m.put(k, v);
    while(m.lastKey() != k) {
      int cand = m.higherKey(k);
      if(m.get(cand) >= v) m.remove(cand);
      else break;
    }
  }
}