  We present a pseudopolynomial-time algorithm for the Knapsack problem that
has running time $\widetilde{O}(n + t\sqrt{p_{\max}})$, where $n$ is the number
of items, $t$ is the knapsack capacity, and $p_{\max}$ is the maximum item
profit. This improves over the $\widetilde{O}(n + t \, p_{\max})$-time
algorithm based on the convolution and prediction technique by Bateni et
al.~(STOC 2018). Moreover, we give some evidence, based on a strengthening of
the Min-Plus Convolution Hypothesis, that our running time might be optimal.
  Our algorithm uses two new technical tools, which might be of independent
interest. First, we generalize the $\widetilde{O}(n^{1.5})$-time algorithm for
bounded monotone min-plus convolution by Chi et al.~(STOC 2022) to the
\emph{rectangular} case where the range of entries can be different from the
sequence length. Second, we give a reduction from general knapsack instances to
\emph{balanced} instances, where all items have nearly the same
profit-to-weight ratio, up to a constant factor.
  Using these techniques, we can also obtain algorithms that run in time
$\widetilde{O}(n + OPT\sqrt{w_{\max}})$, $\widetilde{O}(n +
(nw_{\max}p_{\max})^{1/3}t^{2/3})$, and $\widetilde{O}(n +
(nw_{\max}p_{\max})^{1/3} OPT^{2/3})$, where $OPT$ is the optimal total profit
and $w_{\max}$ is the maximum item weight.
