Money Change
Practice
4.4 (12 votes)
Medium
Approved
Problem
55% Success 129 Attempts 30 Points 1s Time Limit 256MB Memory 1024 KB Max Code

View Russian Translation

Egor is a successful freelance software engineer. He is about to get paid for n projects he has recently finished working on. The cost of the i'th project is \(S_i\) credits. Egor will be getting money for the projects according to the order, i.e. first he will get \(S_1\) credits, then \(S_2\) credits and so on.

Egor likes to get paid in cash. There are k banknotes available in his city, the cost of the i'th banknote is \(W_i\) credits. There is an unlimited amount of each banknote and it's possible to represent any non-negative integer S as some banknote multiset.

Egor has a wallet to keep all the money he has earned. You may think of the wallet as of a banknote sequence. Egor likes to keep the banknotes in his wallet in the non-decreasing order of their costs.

In the beginning, the wallet is empty. Then, each of \(S_i\) is represented as a banknote multiset \(X_i\). Egor calls a sequence \(X_1, X_2, ..., X_n\) an effortless way of getting paid if for each i it's possible to put all the banknotes from \(X_i\) as a subsegment into the current wallet (formed by inserting \(X_1, X_2, ..., X_{i - 1}\) in the same way) so that the banknotes in his wallet are in the non-decreasing order of their costs.

For example, if the current wallet is \([1, 1, 4, 5, 6]\), then it's possible to insert \(X_i = \){\(1, 2, 3, 4\)} the way Egor wants and it's impossible to do the same with \(X_i = \){\(1, 2, 3, 4, 5\)} since the 4 from the wallet doesn't allow to do so.

Your task is calculate the number of effortless ways of getting paid. Two ways are distinct if they aren't equal as sequences of multisets \(X_1, X_2, ..., X_n\).

Input format

The first line of the input contains an integer t denoting the number of test cases.

The first line of the test case description contains two integers n and k. The next line contains k integers denoting \(W_1, W_2, ..., W_k\). The next line contains n integers denoting \(S_1, S_2, ..., S_n\).

Output format

The output should contain a single integer denoting the number of effortless way of getting paid modulo \(1000000009\) (\(10^9 + 9\)).

Constraints

  • \(1 \le t \le 6\)
  • \(1 \le n \le 100\)
  • \(1 \le k \le 10\)
  • \(1 = W_1 < W_2 < ... < W_k \le 5000\)
  • \(1 \le S_i \le 5000\)

Subtasks

Extra constraints Points Which tests
\(n \le 5, k \le 4, S_i \le 20\) 30 1
no extra constraints 70 2

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:30
128 votes
Tags:
GeometryOpenApprovedMedium
Points:30
3 votes
Tags:
ArraysData StructuresMulti-dimensionalMediumMathematics
Points:30
23 votes
Tags:
MathematicsDynamic ProgrammingEasy-MediumApprovedRecursion