799C: Fountains

When one is C and one is D, simple greedily choose the highest beatuty within limit for each type

When both fountains are of the same type, call them F1, F2, if we search for all F1, we need to answer the query, max beauty for all price < T - P(F1). Therefore, we can build such array while we scan through, moreoever, since maxB(v1) >= maxB(v2) whenever v1 > v2, we can bsearch on the weight or value.

Pseudo code

sort the (p, b) tuple by p
maxB(0) = 0
ans = 0;

for i in 1 to n
  maxB(i) = max(maxB(i - 1), PB(i).second) 
  if(PB(i).first < totalValue)
    ans = max(ans, PB(i).second + bsearch(0, i-1))