Moje rozwiązanie w czasie O(n log^2 n):

Najpierw zauważam, że jeśli wybiorę pewien zbiór polan, to najlepiej odwiedzić je wg rosnących a_i. Więc jeśli chcę w pierwszych k dni odwiedzić pewne polany (a1,b1), ..., (ak, bk), to liczba zebranych grzybów wyniesie:
b1 + (a2 + b2) + (2a3 + b3) + ... ((k-1)ak + bk)

To samo można napisać w takiej postaci, która nie zależy od kolejności:
suma_i b_i + suma_(i<j) max(a_i, a_j)

Teraz zauważam, że przechodząc od rozwiązania dla k dni do rozwiązania dla k+1 dni, nie opłaca się wyrzucać polan. Bo jeśli powiedzmy wyrzucimy 3 polany i zastąpimy je 4 innymi, to bardziej się opłaci wziąć te wyrzucone 3 zamiast trzech dodanych o najmniejszych a_i.

Sam algorytm: będziemy dla kolejnych dni znajdować polanę, którą najbardziej się opłaca dodać do zbioru.

Dla każdej polany chcemy trzymać x_i, czyli o ile zwiększy się suma jeśli wybierzemy tę polanę.

Początkowo x_i = b_i. Po dodaniu polany (a_m,b_m), x_i zwiększa się o max(a_m, a_i).

Wszystkie niedodane polany reprezentuję jako punkty na płaszczyźnie o współrzędnych (a_i, x_i).

W każdym kroku muszę zrobić tak:
1. znaleźć najwyższy punkt (największe x_i)
2. usunąć ten punkt (a_m, x_m)
3. wszystkie punkty na lewo od niego podnieść o a_m: (a_i, x_i) -> (a_i, x_i + a_m)
4. wszystkie punkty na prawo od niego przekształcić afinicznie (a_i, x_i) -> (a_i, x_i + a_i)

W tym celu trzymam te wszystkie punkty w pełnym drzewie binarnym posortowanym po a_i. W każdym wierzchołku wewnętrznym reprezentuję górną otoczkę wypukłą punktów poddrzewa, oraz przekształcenie afiniczne tego poddrzewa.

To pozwala znajdować najwyższy punkt wyszukiwaniem binarnym w czasie O(log n), i aplikować przekształcenia afiniczne na poddrzewach.

Po usunięciu punktu i zaaplikowaniu przekształceń afinicznych po obu stronach, muszę policzyć otoczki wypukłe w O(log n) wierzchołkach wewnętrznych. Ale dwie otoczki wypukłe można połączyć znajdując odpowiedni odcinek pomiędzy nimi (most). W każdym wierzchołku wewnętrzym drzewa trzymam tylko ten most.

Most można znaleźć patrząc na wzajemne ułożenie mostów lewej i prawej otoczki. Zależnie od tego, jak one wzajemnie się układają, można wyeliminować z rozważań połowę lewej lub połowę prawej otoczki wypukłej.

Więc szukanie jednej otoczki / jednego mostu zajmuje O(log n), a cała operacja na drzewie O(log^2 n).