eolymp
bolt
Try our new interface for solving problems
Məsələlər

Experiences

Experiences

Zaman məhdudiyyəti 0.5 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

ExperienceОграничение по времени: 200 msОграничение по памяти: 256 MB

Company X has NNN employees. The company has a strict hierarchical tree-like structure – the CEO (Chief Executive Officer) stands at the top (root of the tree), he has some number of direct subordinates, who also have direct subordinates and so on, until we reach regular employees, who have no subordinates (leaves of the tree).

The employees are numbered with integers from 111 to NNN. The CEO has number 111, but the other numbers have nothing to do with the hierarchy. Each employee has some experience – the ithi^{th}i​th​​ employee has experience, denoted by non-negative integer WiW_iW​i​​.

The company has a large number of group projects to complete and the management has decided to split all of the employees into different groups (teams), so that the following conditions are satisfied:

Each team must consist of at least one person and each person must belong to exactly one team.
Each team must consist only of people, who are consecutive subordinates of one another. A group of employees j1,j2,j3,j4,...j_1, j_2, j_3, j_4, ...j​1​​,j​2​​,j​3​​,j​4​​,... is a valid team if j2j_2j​2​​ is directly subordinate of j1j_1j​1​​, j3j_3j​3​​ is a directly subordinate of j2j_2j​2​​, j4j_4j​4​​ is directly subordinate of j3j_3j​3​​ and so on. 

The management knows that after a group project is finished, the total experience of the group, assigned to the project, increases by Wmax−WminW_{\text{max}} - W_{\text{min}}W​max​​−W​min​​, where WmaxW_{\text{max}}W​max​​ is the maximal experience, and WminW_{\text{min}}W​min​​ is the minimal experience among the group members. The total experience increase for the company is equal to the sum of the experience increases of all teams. The management wants to maximize the total experience increase for the company, by splitting the employees into the best possible teams’ configuration, following the two conditions mentioned above.

Nümunə

Giriş verilənləri #1
7
5 5 3 6 2 3 3
1 6
5 3
1 5
6 2
2 4
6 7
Çıxış verilənləri #1
6