import java.util.* ;
interface dp_tgr {
   static void main(String[] z) {
      Scanner sc = new Scanner(System.in) ;
      int b = sc.nextInt() ;
      int n = sc.nextInt() ;
      int INF = 1000000000 ;
      int[] cur0 = new int[b*n], cur1 = new int[b*n], nxt0 = new int[b*n],
            nxt1 = new int[b*n], ta, x = new int[n] ;
      cur1[0] = INF ;
      for (int i=0; i<n; i++)
         x[n-i-1] = sc.nextInt() ;
      int cur0sz = 1 ;
      int cur1sz = 1 ;
      for (int i=0; i<n; i++) {
         int v = x[i] ;
         int nxt0sz = Math.max(cur0sz, cur1sz) ;
         int nxt1sz = Math.max(cur0sz + b - v, cur1sz + b - v - 1) ;
         Arrays.fill(nxt0, 0, nxt0sz, INF) ;
         Arrays.fill(nxt1, 0, nxt1sz, INF) ;
         int both = Math.min(cur0sz, cur1sz) - 1 ;
         if (both < 0)
            both = 1 ;
         nxt1[b - v] = cur1[0] ;
         for (int j=0; j<both; j++) {
            nxt0[j] = Math.min(cur1[j] + v + 1, cur0[j] + v) ;
            nxt1[j + b - v] = Math.min(cur0[j], cur1[j + 1]) ;
         }
         for (int j=both; j<(int)cur0sz; j++) {
            nxt0[j] = Math.min(nxt0[j], cur0[j] + v) ;
            nxt1[j + b - v] = Math.min(nxt1[j + b - v], cur0[j]) ;
         }
         for (int j=both; j<(int)cur1sz; j++) {
            nxt0[j] = Math.min(nxt0[j], cur1[j] + v + 1) ;
            nxt1[j + b - v - 1] = Math.min(nxt1[j + b - v - 1], cur1[j]) ;
         }
         ta = cur0 ;
         cur0 = nxt0 ;
         nxt0 = ta ;
         cur0sz = nxt0sz ;
         ta = cur1 ;
         cur1 = nxt1 ;
         nxt1 = ta ;
         cur1sz = nxt1sz ;
      }
      int r = INF ;
      for (int i=0; i<(int)cur0sz; i++)
         r = Math.min(r, Math.max(i, cur0[i])) ;
      for (int i=0; i<(int)cur1sz; i++)
         r = Math.min(r, Math.max(i, cur1[i])) ;
      System.out.println(r) ;
   }
}