CF1889C1 Doremy's Drying Plan (Easy Version)

The only differences between the two versions of this problem are the constraint on $ k $ , the time limit and the memory limit. You can make hacks only if all versions of the problem are solved. Doremy lives in a rainy country consisting of $ n $ cities numbered from $ 1 $ to $ n $ . The weather broadcast predicted the distribution of rain in the next $ m $ days. In the $ i $ -th day, it will rain in the cities in the interval $ [l_i, r_i] $ . A city is called dry if it will never rain in that city in the next $ m $ days. It turns out that Doremy has a special power. She can choose $ k $ days (in the easy version, $ k = 2 $ ), and during these days it will not rain. Doremy wants to calculate the maximum number of dry cities after using the special power.

N/A

N/A

In the first test case, if Doremy prevents - rain $ 1,2 $ , then city $ 2 $ will be dry; - rain $ 2,3 $ , then no city will be dry; - rain $ 1,3 $ , then no city will be dry; So there is at most $ 1 $ dry city. In the second test case, if Doremy prevents - rain $ 1,2 $ , then city $ 1,2 $ will be dry; - rain $ 2,3 $ , then city $ 4,5 $ will be dry; - rain $ 1,3 $ , then city $ 1,5 $ will be dry. So there are at most $ 2 $ dry cities. In the third test case, it is optimal to prevent rain $ 2,5 $ . In the forth test case, there is always $ 4 $ days of rain that wets all the cities and cannot be prevented.