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
78
79
80
81
82
/*
* author: pavveu
* task: WIN[B]
* time: O(n log n)  
* solution: coordinates change + sorting 
*/

#include <bits/stdc++.h>
using namespace std;

using pii = pair<int,int>;
using vi = vector<int>;
#define all(x) begin(x), end(x)

void go() {
	int n, k; cin >> n >> k;

	// wines = { year, bottles_above }
	// bottles above means how many bottles we have to
	// take including this one, to piramid remain stable
	vector<pii> wines ((n * (n + 1))/2, {0,0});
	vector<vi> coords (n + 1, vi(n + 1, -1));

	// index i means i-th bottle that has been read 
	int index = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			coords[i][j] = index;
			cin >> wines[index].first;

			index++;
		}
	}

	// transfer from i-th index to coordinates (row, col)	
	//  row  col
	//    0   0
	//  1   x   1
	// 2  x   x   2
	//  x   x   x
	//
	// if we know (row, col) coordinates, we can simply 
	// find answer for earch bottles, because is (row + 1)*(col + 1)

	// because we must take off piramid every right and left parent 
	// recursively, so it gives us rectangle of (rows + 1)*(cols + 1) field

	for (int i = 1; i <= n; i++ )  {
		int j = 1;
		while ( (i + j - 1) <= n && coords[i + j - 1][j] != -1) {
			int wineIndex = coords[i + j - 1][j];
			wines[wineIndex].second = i * j; 
			j++;
		}
	}
	
	// sort by year  
	sort(all(wines), [&](const pii & a, const pii & b){ 
		if ( a.first == b.first ) return a.second < b.second;
		else return a.first < b.first; 
		});

	// find smallest year with obtainable steps
	int ans = -1;
	for ( const pii & wine : wines ) {
		int year = wine.first;
		int above = wine.second; 
		
		// cout << "(y: " << year << ", a: " << above << ")\n";
		if ( above <= k ) { ans = year; break; }
	}

	cout << ans << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(0);

	go();

	return 0;
}