Given K <= 100 types of sticks, each stick i having Li units of length, and Pi as prize of the stick and there is an unlimited amount of sticks from each type. We have to connect multiple sticks together so that total length of chosen sticks is exactly N.

I'm struggling to find any solution within the limits of the time limit — 1s, because of the length N which can reach up to 10^9. Can someone give me any techniques required to solve the problem(i know the solution with O(NK) time complexity-not good for time limit), or report if there aren't any.

Thank you :)