Link to problem: https://mirror.codeforces.com/gym/103536/problem/B. (the statement is short so I won't write a summary)
My idea is to use a CHT with the recurrence:
(where the $$$a_i$$$ are sorted), but I dont know how to add a line to the CHT structure, is my approach possible, or is there a different way?
Thanks for your help and attention, have a good day !
There's an observation that if you have $$$a_i \lt = a_j$$$ and $$$b_i \lt = b_j$$$, then it is optimal to put $$$i$$$ and $$$j$$$ in one group. Therefore, $$$i$$$-th cat will not influence the result. Therefore, we can remove cats, values of which are "nested" into other cat. As a result, if you sort $$$a$$$ in increasing order, $$$b$$$ will be sorted in decreasing order. Now, you can do CHT.
beautiful method, I'll try this, thanks for your help sir