Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
Language:
Experiment "X": Explosions Expected
 Time Limit: 20000MS Memory Limit: 64000K Total Submissions: 720 Accepted: 93 Case Time Limit: 1000MS

Description

Unlucky scientist Vasya was tired of permanent mockeries of his colleagues. He built a time machine to go away into the future. But his machine had taken him into the past and then exploded!
Vasya needed some way to earn money! He has taken the job of the Court Alchemist of King Arthur. His first task is to create the philosophers' stone. Vasya has found K ingredients and now conducts experiments which consist in mixing these ingredients in various proportions. More formally, each experiment consists in taking a1 ounces of the first ingredient, a2 ounces of the second and so on. Then all the ingredients are put into the crucible, carefully mixed and heated. All ai are non-negative integers, and their sum does not exceed S -- the capacity of the crucible. In all Vasya's experiments at least two ingredients are taken, i.e. there are at least two ai greater than zero.
But all his experiments have been unsuccessful up to now. All mixtures have exploded! The King is unpleased. Maids of honour complain to Queen Guinevere about these awful explosion sounds! The King has decided to give one last chance to Vasya. Tomorrow Vasya is to conduct his next experiment, which could become the last. If the mixture explodes again, Vasya will be executed.

Fortunately, Vasya has just found way to discard some definitely unsuccessful experiments. He has noted that if for some experiment plan (a1,a2,...,aK) the mixture has exploded, it would explode for any plan (b1,b2,...,bK) such that bi >= ai for all i. Now Vasya wants to count the number of possible experiments which are not definitely unsuccessful according to his unfortunate experience. He has taken out his pocket computer and now he is writing a program which will compute this number. Can you do this?

Input

The first line of input file contains three positive integers 2<=K<= 30, 2<=S<=10000, 0<= M <=20 where M is the number of experiments Vasya has already conducted. The next M lines contain K numbers each, one line per experiment.

Output

Output the number of possible experiment plans for which it is not evident that the mixture would explode.

Sample Input

```2 4 2
1 3
2 1 ```

Sample Output

`2`

Source

Northeastern Europe 2003, Northern Subregion

[Submit]   [Go Back]   [Status]   [Discuss]