#P10728. Useful Swords

    ID: 12761 Type: Default 1000ms 256MiB

Useful Swords

Useful Swords

YH has \(n\) swords. The \(i\)-th sword has an attack power of \(a_i\) and a defense value of \(b_i\). A sword \(i\) is considered useless if there exists another sword \(j\) (with \(j \neq i\)) such that \(a_i \le a_j\) and \(b_i \le b_j\). Otherwise, the sword is considered useful. It is guaranteed that no two swords have both the same attack and defense values, i.e. there do not exist two indices \(i, j\) such that \(a_i = a_j\) and \(b_i = b_j\).

Your task is to determine the number of useful swords among the \(n\) swords.

inputFormat

The first line contains a single integer \(n\) \( (1 \le n)\) which denotes the number of swords. Each of the following \(n\) lines contains two integers \(a_i\) and \(b_i\), representing the attack power and defense value of the \(i\)-th sword.

outputFormat

Output a single integer representing the number of useful swords.

sample

3
1 2
2 1
1 1
2