CF809D Hitchhiking in the Baltic States

Leha and Noora decided to go on a trip in the Baltic States. As you know from the previous problem, Leha has lost his car on the parking of the restaurant. Unfortunately, requests to the watchman didn't helped hacker find the car, so friends decided to go hitchhiking. In total, they intended to visit $ n $ towns. However it turned out that sights in $ i $ -th town are open for visitors only on days from $ l_{i} $ to $ r_{i} $ . What to do? Leha proposed to choose for each town $ i $ a day, when they will visit this town, i.e any integer $ x_{i} $ in interval $ [l_{i},r_{i}] $ . After that Noora choses some subsequence of towns $ id_{1},id_{2},...,id_{k} $ , which friends are going to visit, that at first they are strictly increasing, i.e $ id_{i}

N/A

N/A

Consider the first example. Let's take this plan: let's visit the sight in the second town on the first day, in the third town on the third day and in the fifth town on the fourth. That's would be the optimal answer.