Жақсы жиым


Шешімді жөнелту

Ұпайлар: 0
Уақыт шектеуі: 1.0s
Жад шектеуі: 256M

Problem types

\((a_1,b_1),\ldots,(a_n,b_n)\) жұптарының жиымы берілген. Сіздің тапсырмаңыз: жиымды жақсы қылу. Кез келген \(i = 1, \ldots, n\) үшін келесі шарт қанағаттандырылса, жиымды деп аталады: \[|\{j : a_j = a_i \}| = b_i\] Мұндағы \(|S|\) жиынның өлшемін білдіреді (осы жағдайда \(j\) индекстерінің санын білдіреді). Қарапайым сөзбен айтқанда, \((a_i, b_i)\) жұбы жиымда \(a_j = a_i\) болатын \(j\) жұптарының саны \(b_i\) болу керек деген шектеу қояды.

Бір операцияда жиымға кез келген жаңа \((x,y)\) жұбын қосуға немесе жиымнан кез келген бар жұпты жоюға рұқсат етіледі. Жиымды жақсы ету үшін қажетті операциялардың ең аз санын анықтаңыз.

Input

Бірінші жолда бір сан \(n\) (\(1\le n \le 2 \cdot 10^5\)) бар – жиынның бастапқы өлшемі.

Келесі \(n\) жолдың әрқайсысы екі саннан тұрады, \(i\)-ші жолда \(a_i\) және \(b_i\) (\(1\le a_i \le 10^9, 1 \le b_i \le n\)) сандары бар – жиынның ішіндегі жұптар.

Output

Бір бүтін сан шығарыңыз — жиымды жақсы қылу үшін қажетті операциялардың ең аз саны.

Sample Input 1

6
4 3
2 5
4 5
4 3
2 5
5 1

Sample Output 1

4

Sample Input 2

3
1 3
1 3
1 3

Sample Output 2

0

Notes

Бірінші мысалда келесідей операциялар орындауға болады:

  • Жиымнан \((2, 5)\) жұбын алып тыстау.

  • Жиымнан тағы бір \((2, 5)\) жұбын алып тыстау.

  • Жиымға \((4, 3)\) жұбын қосу.

  • Жиымнаң \((4, 5)\) жұбын алып тыстау.

Соңында бізде жақсы жиым \((4, 3), (4, 3), (4, 3), (5, 1)\) қалады. \(4\)-тен кем операция орындап жиымды жақсы қылуға болмайтынын көрсетуге болады.

Екінші мысалда жиым бастаптыда жақсы болады, сондықтан ешқандай операция қажет емес.


Пікірлер

Қазіргі уақытта ешқандай пікір жоқ.