z-Attack
Soren, a traveling monk warrior, is in a big hurry-he needs to find a restroom, fast! He dashes into a nearby city and accidentally bumps into one of the srongest fighters around, Frank the Fearless. Frank (much to Soren's dismay) begins to attack Soren. Soren, being the faster in reflexes, has decided to end this fight fast by using a K-move karate combo
Soren can use N different attacks, each of them giving Di damage.
Help Soren decide the number different ways he can take out Frank, and hence find a bathroom, using exactly K of his moves.
InputThe first line of the standard input contains the number 1<=S<=100000, where S is Frank's stamina, followed by 1<=N<=22 and 1<=K<=N.
In the next line there are N numbers 1<= Di <=100000;
In the next line there are N numbers 1<= Di <=100000;
OutputTo the standard output write one number that is the number of ways Soren can defeat Frank using K of his attacks.
Note: each attack can only be used once in the fight, and the order at which the attacks are executed in a combo is irrelevant.
Note: each attack can only be used once in the fight, and the order at which the attacks are executed in a combo is irrelevant.
Input:
10 5 3
3 4 4 4 3
Output:
10Here, any 3 attack combo would defeat Frank.
Submit solution
Coming laterThe grading service will be connected in a later migration step. You can inspect the task and your previous results now.