Przedziały

Limit pamięci: 32 MB

Przedziałem (gdzie ) nazywamy zbiór liczb całkowitych niemniejszych niż i niewiększych niż .

Dany jest zbiór zawierający przedziałów. Twoim zadaniem będzie wyznaczenie minimalnej liczby rozłącznych przedziałów, których suma jest taka sama jak suma przedziałów ze zbioru .

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia liczbę całkowitą oraz przedziałów należących do zbioru ,
• wypisze na standardowe wyjście jedną liczbę całkowitą, będącą minimalną liczbą rozłącznych przedziałów, których suma jest taka sama, jak suma przedziałów ze zbioru .

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę całkowitą (). Kolejne wierszy zawiera opis kolejnych przedziałów należących do zbioru . Opis każdego z przedziałów składa się z 2 liczb () oddzielonych pojedynczym odstępem. Liczby reprezentują przedział .

Wyjście

Wyjście powinno zawierać dokładnie jedną liczbę całkowitą, będącą minimalną liczbą przedziałów, których suma jest taka sama jak suma przedziałów ze zbioru .

Przykład

Dla danych wejściowych:

4
-2 2
6 6
0 3
5 5

poprawną odpowiedzią jest:

2