لتلبية تزايد حاجات $N$ أبقار ($1 \le N \le 50,000$) اشترى Farmer John آلة مشروب غازي ويبحث عن أفضل موضع.

المرعى خط أعداد. البقرة $i$ ترعى في $A_i..B_i$ ($1 \le A_i \le B_i; A_i \le B_i \le 1,000,000,000$)، شاملًا الطرفين. الآلة بأي نقطة صحيحة من $1..1,000,000,000$. لكسل الأبقار تريد أقل حركة وآلة ضمن نطاقها.

لا يمكن دائمًا إرضاء الجميع. يريد FJ أكبر عدد راضٍ.

نطاقات أربع بقرات $3..5$ و$4..8$ و$1..2$ و$5..10$ موضحة أدناه:

         1   2   3   4   5   6   7   8   9  10  11  12  13
         |---|---|---|---|---|---|---|---|---|---|---|---|-...
                 aaaaaaaaa
                     bbbbbbbbbbbbbbbbb
         ccccc           ddddddddddddddddddddd

الأولى والثانية والرابعة تشترك بـ$5$، والثالثة منفصلة. أقصى عدد 3 ضمن نطاقها الآلة.

الإدخال

• السطر 1: الصحيح $N$.
• الأسطر $2..N+1$: السطر $i+1$ الصحيحان $A_i$ و$B_i$ تفصلهما مسافة.

الإخراج

• السطر 1: صحيح، أكبر عدد بقرات يمكن أن تحتوي نطاقاتها كلها الآلة.

أمثلة

الإدخال 1

4
3 5
4 8
1 2
5 10

الإخراج 1

3

ملاحظة

عند $5$ ترضى 1 و 2 و 4؛ إرضاء الأربع مستحيل.

مؤلف المسألة: Neal Wu، 2008.