You need a couple of observations:

First, if there are some cats $$$i, j$$$ such that $$$a_i \le a_j$$$ and $$$b_i \le b_j$$$ then it's optimal to put the cat $$$i$$$ on the same group as cat $$$j$$$. We can ignore the cat $$$i$$$. Therefore we can sort all cats by $$$(a_i, b_i)$$$ and erase all these "useless" cats, getting at the end an array where the cats are sorted strictly increasing by $$$a_i$$$ and strictly decreasing by $$$b_i$$$.

Other observation: now with this new array, it's optimal to group consecutive cats.

Therefore now you can use the following DP:

$$$dp[i]$$$: min cost of partitioning the prefix until position $$$i$$$. The transitions are:

Now you can apply easily Convex Hull Trick here. You can get linear complexity, because the slopes are sorted and the points of the queries to your DS are sorted too.