题目描述

Amazin’ Inc, an up-and-coming company in e-commerce, has recently optimized its operations to make the most out of its workers. Thanks to state-of-the-art prediction methods, Amazin’ now knows in advance how many workers will be needed each day for the foreseeable future. Using this information they can adjust the size of their workforce on a day-to-day basis by firing and/or hiring workers so that they always have exactly as many as are needed each day. In order to prevent the workers from getting too comfortable and organizing themselves, they will also regularly fire workers and replace them with new ones. For instance, if on some day four more workers are needed than yesterday, Amazin’ might fire 10 people and then hire 14 new ones on that day.

Unfortunately, due to labor laws, the firing of workers must follow a last-in-first-out order: the people who have been employed the shortest time must be fired first. Furthermore, a fired person cannot be re-hired within the foreseeable future so it is not possible to circumvent the law by firing some people and then immediately re-hiring some of them.

But this story is actually about HR, not workers! Every day, one employee from the HR department is assigned to be responsible for giving the fired workers the bad news that they are fired, and for then giving the newly hired workers the good news that they are hired. In order to minimize work environment problems in the form of social awkwardness for the HR staff, a policy has been established requiring that the HR person firing an employee must always be a different HR person than the one welcoming them when they were hired.

Now the time has come for the HR department to also optimize itself, by making itself as small as possible. Unlike workers, new HR staff cannot be hired with short notice, so the HR personnel must be permanent employees. What is the smallest number of HR people needed in order to manage all the planned hirings and firings?

输入格式

输出格式

样例

4 
0 3 
1 1 
2 1 
2 0

3 
1 2 3 2

6 
0 10 
0 5 
2 0 
0 0 
0 100 
50 100

2 
1 2 1 2 1 2

提示

by 20jifengzhiyin