该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

InRepublicofJOI,thereare N stationsnumberedfrom1to N. Theyarelocatedclockwiseonacircularrailway in order. There are N types of train tickets numbered from 1 to N. By using one ticket of type i (1 ≤ i ≤ N −1), one personcantravelfromthestationitothestationi+1,orfromthestationi+1tothestationi. Byusingoneticket of type N, one person can travel from the station 1 to the station N, or from the station N to the station 1. We can only buy a package of N tickets consisting of one ticket for each type. You are working at a travel agency in Republic of JOI. Your task is to arrange tickets for customers. Today,youhave M requestsforarrangingtickets. Thei-threquestsaysCi peoplewanttotravelfromthestation Ai to the station Bi. TheseCi people need not to take the same route when they travel. You want to know the minimum number of packages of tickets you need to buy in order to deal with all the requests.