0


# include[HTML_REMOVED]

using namespace std;

const int N = 1007;

int n, m;
char str1[N], str2[N];
int p[N][N];

// 这次p[i][j]代表的是str1的前i个字符变换成str2的前j个字符,需要经过的最少变换次数
int main()
{
cin >> n >> str1 + 1;
cin >> m >> str2 + 1;

// 初始化
for (int i = 0; i <= m; i ++) p[0][i] = i; // 当str1长度为零的时候,对应的操作只能是删除,操作次数就是str2的长度i
for (int i = 0; i <= n; i ++) p[i][0] = i; // 当str2长度为零的时候,对应的操作只能是插入,操作次数就是str1的长度i

for (int i = 1; i <= n; i ++)
for (int j = 1; j <= m; j ++)
{
p[i][j] = min(p[i - 1][j], p[i][j - 1]) + 1;
if (str1[i] == str2[j]) p[i][j] = min(p[i][j], p[i-1][j-1]);
else p[i][j] = min(p[i][j], p[i - 1][j - 1] + 1);
}
cout << p[n][m] << endl;
return 0;


}

#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1007;
int n, m;
char str1[N], str2[N];
int p[N][N];

int main()
{
cin >> n >> m;
cin >> str1 + 1 >> str2 + 1;

for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
p[i][j] = max(p[i - 1][j], p[i][j - 1]);
if (str1[i] == str2[j]) p[i][j] = max(p[i][j], p[i - 1][j - 1] + 1);
}
}
cout << p[n][m] << endl;
return 0;
}


// 开放寻址法：
#include<iostream>
#include<cstring>

using namespace std;

const int N = 2e5 + 3, null = 0x3f3f3f3f;
int p[N];

int find (int a)
{
int c = (a % N + N) % N;
while (p[c] != null && p[c] != a)
{
c ++;
if (c == N + 1) c = 0; // 如果到头了，就回到开始的位置。
}
return c;
// 这个函数返回的是 a 应该呆在的位置
}

int main()
{
memset(p, 0x3f, sizeof p); // 赋初值,0x3f3f3f3f;
int m;
cin >> m;
while (m --)
{
char op[2];
int a;
scanf("%s%d",op, &a);
int k = find(a); if (*op == 'I') p[k] = a;
else
{
if (p[k] != 0x3f3f3f3f) puts("Yes");
else puts("No");
}
}
return 0;
}


#include<iostream>
#include<cstdio>

using namespace std;

const int N = 1007;
int n;
int arr[N], p[N];
int ans;

int main()
{
cin >> n;
for (int i = 1; i <= n; i ++) scanf("%d", &arr[i]);

for (int i = 1; i <= n; i ++)
{
p[i] = 1;
for (int j = 1; j <= i; j ++)
{
if (arr[i] > arr[j]) p[i] = max(p[i], p[j] + 1);
}
ans = max(ans, p[i]);
}
cout << ans << endl;
return 0;
}


#include<iostream>
using namespace std;
const int N = 107;
int n, m;
int p[N], v[N], w[N];
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int s;
cin >> s;
for (int j = 1; j <= s; j ++) cin >> v[j] >> w[j];

for (int j = m; j >= 1; j --)
for (int k = 1; k <= s; k ++)
if (j >= v[k])
p[j] = max( p[j], ( p[j - v[k]] + w[k] ) );
}
cout << p[m] << endl;
return 0;
}
// 根据题意，每层i循环，都只需要用到当前这一层的w,v。所以可以覆盖输入。


#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;
// log 2 (2000) = 11
const int N = 2007, M = 11000;
int n, m;
int v[M], w[M], cnt;
int p[N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++)
{
int v1, w1, s1;
scanf("%d%d%d", &v1, &w1, &s1);
int k = 1;
while (k <= s1)
{
cnt ++;
v[cnt] = k * v1, w[cnt] = k * w1;
s1 -= k;
k *= 2;
}
if (s1 > 0) v[++ cnt] = s1 * v1, w[cnt] = s1 * w1;
}

for (int i = 1; i <= cnt; i ++)
{
for (int j = m; j >= v[i]; j --)
{
p[j] = max(p[j], p[j - v[i]] + w[i]);
}
}

cout << p[m] << endl;

return 0;
}


#include<iostream>
#include<cstdio>

using namespace std;

const int N = 107;
int n, m;
int s[N], v[N], w[N];
int arr[N][N];

int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i ++) scanf("%d%d%d", &v[i], &w[i], &s[i]);

for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= m; j ++)
{
for (int k = 0; k <= s[i]; k ++)
{
if (j >= v[i] * k) arr[i][j] = max(arr[i][j], arr[i - 1][j - k * v[i]] + w[i] * k);
}
}
}
cout << arr[n][m] << endl;
return 0;
}


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1e5 + 7;
int n, cnt, res;

struct range
{
int l, r;
bool operator< (const range &w) const
{
return w.l > l;
}
}ranges[N], ran[N];

int main()
{
int st, ed;
cin >> st >> ed;
cin >> n;

for (int i = 0; i < n; i ++)
{
int a, b;
cin >> a >> b;
if (!(b < st || a > ed))
ran[cnt ++] = {a, b};
}

sort(ran, ran + cnt);

bool success = false;

for (int i = 0; i < cnt; i ++)
{
int j = i, t = -2e9;
while (j < cnt && ran[j].l <= st)
{
t = max(t, ran[j].r);
j ++;
}

if (t <= st) break;

res ++;

if (t >= ed)
{
success = true;
break;
}

st = t;
}
if (success == true) cout << res << endl;
else puts("-1");
return 0;
}


#include<iostream>
#include<queue>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N = 1e5 + 7;
int n;
struct ranger
{
int l, r;
bool operator< (const ranger &W) const
{
return l < W.l;
}
}arr[N];

int main()
{
cin >> n;
for (int i = 0; i < n; i ++)
{
int l, r;
scanf("%d%d", &l, &r);
arr[i] = {l, r};
}

sort(arr, arr + n);

priority_queue<int, vector<int>, greater<int>> heap; // 定义小根堆

for (int i = 0; i < n; i ++)
{
ranger t = arr[i];
if (heap.empty() || heap.top() >= t.l) heap.push(t.r);
else
{
heap.pop();
heap.push(t.r);
}
}
printf("%d\n", heap.size());
return 0;
}