This is a basic application of knapsack DP; let \(dp_i[j] \in \{0, 1\}\) indicate whether it’s possible, considering the first \(i\) types of coins, to pay \(j\) yen. A pretty simple transition from \(dp_i[j] = 1\) to \(dp_{i+1}[k]: k \in \{ j, j + A_i, j + 2A_i, ..., j + B_iA_i\}\) should solve this problem in \(O(NXB)\), which should pass.

It’s possible to optimize to \(O(NX)\); note that if we iterate through \(dp_i[j]\) with descending \(j\) to transition to \(dp_{i+1}\), if when marking \(dp_{i+1}[k]: k \in \{ j, j + A_i, j + 2A_i, ..., j + B_iA_i\}\), we encounter a value that’s already been set to \(1\), the rest of the values we wish to mark are also already \(1\), so we can break early.