Problem link (The problem is originally from ONTAK 2007, but I can't find it from szkopul.edu.pl)

Statement: $$$N$$$ people wants to cross the river with a boat. In each step, two people will take the boat to cross the river, and if necessary, one of those two will come back with a boat to salvage the remaining people. Each people have a *time factor* $$$t_i$$$, and the time boat needs to cross the river is equal to the maximum time factor of all people on the boat. Additionally, there are $$$M$$$ pairs of people, who don't want to be in the boat at the same time. What is the minimum time needed for all people to cross the river? Print `NIE`

if this is impossible at all. ($$$2 \le N \le 100\,000, 0 \le M \le 100\,000$$$)

I can solve this problem in polynomial time, but I don't think this approach can be optimized, nor have I found any alternative approach.

**Spoiler**

The problem is almost 20 years old, but it's really hard. Anyone knows how to solve this?