//#include <iostream>
//using namespace std;
//int main()
//{
// // printf
// cout << "Hello world!" << endl;
//
// int x, y;
//
// cin >> x >> y;
//
// cout << x << "+" << y << "=" << x + y << endl;
// return 0;
//}
//#include<iostream>
//
//using namespace std;
//
//int main() {
//
// for(int i=0; i<5; i++) {
// cout << i << endl;
// }
//}
//#include<iostream>
//
//using namespace std;
//
//int main() {
// int n;
//
// cin >> n;
//
// int arr[n] = {0};
//
// for(int i = 0; i < 5; i++) {
// int v[100] = {0};
// }
// cout << v[10] << "\n";
//}
/*
#include <iostream>
#include <queue>
using namespace std;
int v,e,k,p[20010][20010] = {},sr[20010] = {},vis[20010] = {};
int main(){
cin >> v >> e >> k;
for(int i = 0; i <= v; i++) sr[i] = 999999999;
sr[k] = 0;
int x, y, w;
for(int i = 0; i < e; i++){
cin >> x >> y >> w;
if(p[x][y] == 0 || p[x][y] > w) p[x][y] = w;
}
int z = k;
queue<int> q1;
queue<int> q2;
q1.push(k);
q2.push(0);
while(!q1.empty()){
int a = q1.front(), d = q2.front();
q1.pop();
q2.pop();
if(z != a) vis[z] = 1;
z = a;
if(d < sr[a]) sr[a] = d;
for(int i = 1; i <= v; i++){
if(vis[i] == 0 && p[a][i] != 0 && sr[i] > sr[a] + p[a][i]){
q1.push(i);
q2.push(sr[a] + p[a][i]);
}
}
}
for(int i = 1; i <= v; i++){
if(sr[i] > 10) cout << "INF" << "\n";
else cout << sr[i] << "\n";
}
return 0;
}
*/
/*
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n,k, arr[60][60] = {};
cin >> n >> k;
for(int i = 0; i < n; i++){
cin >> arr[i][0] >> arr[i][1];
}
int m = 0, b = 2047483647;
if(k == 1){
for(int i = 0; i < n; i++){
m = 0;
for(int a = 0; a < n; a++){
int d = abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1]);
if(d > m) m = d;
}
if(m < b) b = m;
}
}
else if(k == 2){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
m = 0;
for(int a = 0; a < n; a++){
int d = (abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1])) < (abs(arr[j][0] - arr[a][0]) + abs(arr[j][1] - arr[a][1])) ? (abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1])) : (abs(arr[j][0] - arr[a][0]) + abs(arr[j][1] - arr[a][1]));
if(d > m) m = d;
}
if(m < b) b = m;
}
}
}
else{
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
for(int h = 0; h < n; h++){
m = 0;
for(int a = 0; a < n; a++){
int d = ((abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1])) < (abs(arr[j][0] - arr[a][0]) + abs(arr[j][1] - arr[a][1])) ? (abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1])) : (abs(arr[j][0] - arr[a][0]) + abs(arr[j][1] - arr[a][1]))) < (abs(arr[h][0] - arr[a][0]) + abs(arr[h][1] - arr[a][1])) ? ((abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1])) < (abs(arr[j][0] - arr[a][0]) + abs(arr[j][1] - arr[a][1])) ? (abs(arr[i][0] - arr[a][0]) + abs(arr[i][1] - arr[a][1])) : (abs(arr[j][0] - arr[a][0]) + abs(arr[j][1] - arr[a][1]))) : (abs(arr[h][0] - arr[a][0]) + abs(arr[h][1] - arr[a][1]));
if(d > m) m = d;
}
if(m < b) b = m;
}
}
}
}
cout << b;
return 0;
}
*/
/*
#include <iostream>
using namespace std;
int main(){
int n,k,x,y;
cin >> n >> k;
for(int i = 0; i < n-1; i++) cin >> x >> y;
cout << n / k;
}
*/
/*
#include <iostream>
using namespace std;
int main(){
int t,n,m,k,d,a,b;
cin >> t;
for(int i = 0; i < t; i++){
cin >> n >> m >> k >> d;
int y = m - 1, z = (n - 1) * m;
int a = k, b = 1, s = (a y + b z) * m, x = -1;
while(s <= d){
x = 0;
b++;
a = k * b;
s = (a y + b z) * m;
}
b--;
a = k * b;
s = (a y + b z) * m;
if(x != -1) cout << s << "\n";
else cout << "-1" << "\n";
}
return 0;
}
*/
/*
#include <iostream>
using namespace std;
int n, arr[300010][2] = {};
int main(){
cin >> n;
for(int i = 0; i < n; i++){
cin >> arr[i][0];
int m = 0;
for(int j = 0 ; j < i; j++){
if(arr[i][0] % 2 != arr[j][0] % 2 && arr[j][1] > m) m = arr[j][1];
}
arr[i][1] = m + 1;
}
int s = 0;
for(int i = 0; i < n; i++){
if(arr[i][1] > s) s = arr[i][1];
}
cout << s;
return 0;
}
*/