1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <cstdio>
#include <algorithm>
using namespace std;
int cache[2001*1000];

struct Loc{
  int col;
  int row;
  Loc(int col, int row) : col(col), row(row){}
  Loc(){}
};

int get_index(Loc loc){
   return loc.row*(loc.row+1)/2+loc.col;
}
int get_index(int row, int col){
   return get_index(Loc(col,row));
}

Loc left_up(Loc loc){
  return Loc(loc.col-1, loc.row-1);
}

Loc right_up(Loc loc){
  return Loc(loc.col, loc.row-1);
}

Loc double_up(Loc loc){
  return Loc(loc.col-1, loc.row-2);
}

int bottles(Loc loc){
//  printf("%d %d\n", loc.row, loc.col);
   if(loc.row==0 && loc.col==0) return 1;
   if(loc.row<0) return 0;
   if(loc.col<0 || loc.col>loc.row) return 0;

   int index = get_index(loc);
   if(cache[index]!=0)
     return cache[index];

   cache[index] = 1 + bottles(left_up(loc))+ bottles(right_up(loc))-bottles(double_up(loc));
   return cache[index];
}

int main(){
//  Loc x = Loc(10,20);
//  printf("%d %d\n", x.col, x.row);
  int n,k;
  scanf("%d%d", &n, &k);
  int T[n*(n+1)/2+1]; 
  for(int i=0; i<n; i++)
    for(int j=0; j<=i; j++){
      scanf("%d", &T[get_index(i,j)]);
      bottles(Loc(j,i));
    }

  int all = n*(n+1)/2;
  int result = 3000;
  for(int i=0; i<all ;i++){
//    printf("%d ", cache[i]);
    if(cache[i]<=k)
      result = min(result, T[i]);
  }
//  printf("\n");
//  for(int i=0; i<n; i++){
//      for(int j=0; j<=i; j++)
//        printf("%d ", cache[get_index(i,j)]);
//      printf("\n");
//   }


  printf("%d\n", result);

    
  return 0;
}