Vova kompüterdə «Robot və xəzinə» adlanan çox maraqlı oyun oynayır. Bu oyunda sonsuz sayda xanalardan ibarət olan sahədə bəzi xanalarda qiymətli əşyalar olan sandıqlar var. Oyunçuya robotu əvvəlcə xanalardan birinə yerləşdirdikdən sonra isə bütün xəzinəni toplamaq üçün onu idarə etmək təklif olunur. Robot olduğu xanadakı qiymətli maddi obyekti götürür. Robot istənilən qonşu xanaya gedə bilər. O bunu klaviaturada xüsusi düyməni sıxmaqla edir.

Bu yaxınlarda Vovaya bədbəxtçilik üzv verdi. Onun klaviaturasında bir neçə düymə xarab oldu, lakin buna baxmayaraq o bütün xəzinəni toplaya bildi. İndi Vovanı bir sual maraqlandırır, istənilən halda bütün xəzinəni toplaya bilmək üçün o maksimal sayda nə qədər düyməni xarab edə bilər.

Giriş verilənləri

Giriş faylının birinci sətrində qiymətli əşyalar olan sandıqların sayı - n tam ədədi verilir. Sonra hər birində növbəti sandığın koordinatlarını ifadə edən 2 tam ədədi ehtiva edən n sətir verilir.

Məhdudiyyət

• n ədədi üçün 1 ≤ n ≤ 1000 bərabərsizliyi doğrudur.
• Giriş faylındakı bütün digər ədədlər mütləq qiymətcə 105-i aşmır.

Çıxış verilənləri

Çıxış faylında yeganə ədədi - xarab edilə biləcək klaviatura düymələrinin maksimal sayını verin.