Búp bê lồng nhau (Nested Dolls)

Nguồn: UVa

Phiên bản: Phước Hưng OJ Extended

Đề bài

Có $m$ búp bê rỗng. Búp bê $i$ có chiều rộng $w_i$ và chiều cao $h_i$.

Búp bê $(w_1,h_1)$ có thể đặt hoàn toàn vào búp bê $(w_2,h_2)$ khi và chỉ khi

Một nhóm búp bê lồng nhau là một chuỗi trong đó mỗi búp bê nằm trong búp bê kế tiếp. Mỗi búp bê phải thuộc đúng một nhóm.

Hãy tìm số nhóm búp bê lồng nhau ít nhất có thể.

Input

• Dòng đầu chứa $m$.
• Dòng thứ hai chứa $2m$ số $w_1,h_1,w_2,h_2,\ldots,w_m,h_m$.

Output

In số nhóm ít nhất.

Subtask

• Subtask 1 — 20%: $m\le100$.
• Subtask 2 — 30%: $m\le5000$.
• Subtask 3 — 50%: $1\le m\le20000$, $1\le w_i,h_i\le10000$.

Ví dụ

Input

4
20 30 10 10 30 20 40 50

Output

2

Giải thích

Có thể tạo hai chuỗi, chẳng hạn $(10,10)\to(20,30)\to(40,50)$ và $(30,20)$. Không thể đưa cả bốn búp bê vào một chuỗi vì $(20,30)$ và $(30,20)$ không chứa được nhau.