P10728 [NOISG 2023 Qualification] Swords

题目描述

YH 有 $n$ 把剑,第 $i$ 把剑的攻击力为 $a_i$,防御能力为 $b_i$。 对于一把剑 $i$,如果存在一个 $j(j \not = i)$,使得 $a_i\le a_j$ 且 $b_i\le b_j$,那么 YH 就认为这把剑是无用的。反之,他就认为这把剑是有用的。 在本题中,我们保证,不可能找到两把剑 $i,j$,使得 $a_i=a_j$ 且 $b_i=b_j$。 请你帮助 YH 求出这 $n$ 把剑中,有用的剑的数量。

输入格式

第一行,一个整数 $n$。 接下来 $n$ 行,每行两个整数 $a_i,b_i$,表示第 $i$ 把剑形的攻击力和防御能力。

输出格式

一个整数,表示有用的剑**的数量**。

说明/提示

|$\text{Subtask}$|分值|特殊性质| |:-:|:-:|:-:| |$1$|$11$|$n\le500$| |$2$|$21$|$a_i,b_i\le500$| |$3$|$34$|$a_i=i$| |$4$|$25$|对于每一个 $1\le i