|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|4 초||256 MB||1||1||1||100.000%|
In Republic of JOI, there are N stations numbered from 1 to N. They are located clockwise on a circular railway 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 person can travel from the station i to the station i + 1, or from the station i + 1 to the station i. By using one ticket 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, you have M requests for arranging tickets. The i-th request says Ci people want to travel from the station Ai to the station Bi. These Ci 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.
Given the number of stations and information of requests, write a program which calculates the minimum number of packages of tickets you need to buy.
Read the following data from the standard input.
Write one line to the standard output. The output contains the minimum number of packages of tickets you need to buy.
3 3 1 2 1 2 3 1 3 1 1
If everybody travels clockwise, you need one ticket for each type. Hence you need to buy one package of tickets.
3 2 1 2 4 1 2 2
You need three tickets for each type if people travel in the following way:
Hence it is enough to buy three packages of tickets.
We output 3 because it is impossible to travel if you buy only two packages.
6 3 1 4 1 2 5 1 3 6 1
For example, you buy two packages of tickets, and distribute them in the following way:
We output 2 because it is impossible to travel if you buy one package only.