\(x \leq 10^9\) を見ていなくて1WA。

dp とわかったが、実装できず。