Primero algunas observaciones:

• si ~A_i < A_j~, y no se paga ni por ~i~ ni por ~j~, entonces ~i~ se conecta primero que ~j~.

• Es mejor realizar primero todas las conexiones pagadas, y luego las conexiones gratis.

Por lo cual se pueden ordenar los pares de la entrada, y de este arreglo, se selecciona un subconjunto, se paga, y el resto se conecta en orden. Con esto se puede resolver el problema en ~O(2^n\cdot{n})~ lo cual es suficiente para la subtarea 1.

Al arreglo ~A~, despues de ordenado, a cada posición se le puede restar ~i - 1~ (porque se sabe que los ~i - 1~ elementos anteriores que el se conectarán antes que el a no ser que ~i~ sea comprado, caso en el cual no importa ~A_i~) y queda como resultado la cantidad de personas ~C_i = A_i - ( i - 1 )~ que se tienen que comprar ~j \geq i~ debido a la restricció de la persona ~i~.

Se puede resolver ahora con ~dp~ el problema analizando si se compra o no cada elemento en de ~n~ a ~1~, ~dp_{i,j}~ significa comprando ~j~ conexiones en el sufijo ~i~, las transiciones son comprar la persona ~i~ y moverse a ~dp_{i-1,j+1}~ o no comprarla y moverse a ~dp_{i-1,j}~ si ~C_i \leq j~. Con esta ~dp~ en ~O(n^2)~ se pueden alcanzar la subtarea 2.

Se puede notar que al comprar el ~i~-ésimo elemento es como si se restara ~1~ a ~C_j~ para ~1 \leq j < i~, y entonces un elemento se puede comprar si ~C_j \leq 0~.

Además se tiene que ~C_{i+1} + 1 \geq C_i~ para todo ~i~, por lo que en el caso de que todos cuesten ~1~ la solución siempre va a ser un prefijo del arreglo (ordenado) (subtarea 3).

Debido a las observaciones que hemos hecho hasta ahora, se puede elaborar un algoritmo greedy, recorremos ~i~ de ~n~ a ~1~, manteniendo un conjunto ~S~ de las conexiones que podemos comprar, en cada paso añadimos ~B_i~ a ~S~ y mientras la cantidad de gente que hemos comprado es menor que ~C_i~, compramos la conexión mas barata posible, la complejidad es ~O(n\log{n})~ si se usa una priority queue o un set, la prueba de este algoritmo se deja como un corto ejercicio al lector.