BOOKWORM - Kuchu the Bookworm
In this problem, you’ll be helping a little bookworm, Kuchu.
Recently “Omuk book shop” has announced a huge sale on various books. Being a bookworm, Kuchu could not miss this opportunity and went there immediately!
When reached there, she noticed that conditions of the sale are:
- One must buy exactly B books to get the discount.
- Maximum number of pages in any book is no more than 100.
As she wants to read as much as possible, Kuchu wants to get maximum number of pages satisfying the conditions above. Now she is wondering if there are N books in the store, how many different ways are there to choose exactly B books so that the number of pages is maximum possible.
Not all books are interesting to little kids, so you are given two information about each book-
- Number of pages P.
- Interest value V. V is 1 if the book is interesting for kids and 0 otherwise.
Input
First line contains an integer T, the number of test cases.
For each test case, the first line contains two integers N and B as mentioned above. Next N lines contain two integers each Pi and Vi, number of pages and interest factor of ith book.
1 ≤ T ≤ 25
1 ≤ N ≤ 100,000
1 ≤ B ≤ N
1 ≤ Pi ≤ 100
0 ≤ Vi ≤ 1
Output
For each test case, print one integer, the number of different ways to choose exactly B interesting books from those N books so that the number of pages is maximum possible. As result can be pretty large, print it modulo 1,000,000,007 (10^9+7).
Example
Input:2
Output:
2 1
2 0
3 0
5 3
10 0
5 1
2 1
2 1
2 10
3
hide comments
nadstratosfer:
2019-07-26 20:05:40
Useless TL prevents AC in Python. Downvote. |
|
sajid:
2017-07-11 00:30:25
Can anyone give a test case? |
|
Evan:
2016-09-23 07:58:55
@DHEERAJ: Don't know why you got TL, might be SPOJ's issue, now your submission get WA. |
|
DHEERAJ KUMAR:
2016-05-12 11:09:32
@Evan : submission id 16903603. Can u Please check why am i getting TLE. Complexitiy O(T*n) |
|
Evan:
2016-05-10 13:13:29
@Vikneshwar, I've seen your submission and it's not O(N) of course. Try optimizing :) |
|
Vikneshwar E:
2016-04-30 19:08:35
@Evan : Submission ID 16845370. Can you please check why I am getting TLE for this solution. Mine is O(N) only. |
|
Vipul Srivastava:
2016-04-28 11:51:15
Ya C++4.3.2 is giving TLE |
|
Evan:
2016-04-28 11:42:13
@ (^_^) : That's strange! Your solution works as intended when submitted in C++14. There might be some issue with C++. |
|
Vipul Srivastava:
2016-04-28 10:22:47
O(B) algo gives TLE since B can be upto N so that is the time to scan the input.
|
|
(^_^):
2016-04-28 10:18:38
I am only scanning the inputs and printing 0 but still giving TLE. Is there something wrong with the question?
|
Added by: | Evan |
Date: | 2016-04-27 |
Time limit: | 0.400s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: GOSU |
Resource: | From NHSPC 2016 Final Round.http://www.nhspc.org/ |