Submit Best Submissions All Submissions

325. Course Scheduling

Problem Statement:
Heba Gamal, one of the best contestants of Coach Mohamed Abd El-Wahab's (aka. Fegla) trainees. She got the 3rd place with her team in the ECPC'13. Yes, she is the strongest ACM/ACPC girl on the Arab region ever.

Heba currently is working on a company besides being a contestant. She had a trouble with her CEO Amr Hussein, who was himself a contestant and the teammate of her coach Fegla at ANARC 2002. Heba is a pre-master student, and wants to register the courses of this semester without having a conflict with her working times. She reached an agreement with her CEO to give her some free times during the week to attend her lectures. Heba calculated her schedule for the semester N weeks. She has M courses(one lecture per week for each course) and for each course, she knows the maximum number of lectures she can attend. It's known that if she didn't attend at least half of the semester lectures for any course, she won't get its grade.

Tell Heba what's is the maximum number of courses she can register peacefully with her CEO.

Input Format:
An integer T (1 ≤ T ≤ 10) representing the number of test cases. Each test case consists of two lines. First line contains N and M (1 ≤ N ≤ 1, 000, 000) (1 ≤ M ≤ 100, 000) where N is the number of weeks per semester and M is the number of courses per semester. Second line consists of M integers Mi (0 ≤  Mi  ≤ N) where Mi is the maximum number of lectures she can attend for course i.

Output Format:
For each case you should output: "Case X: Y" where X is the case number starting from 1, and Y is the maximum number of courses.

Sample Input:
1 13 7 6 6 7 8 5 9 1

Sample Output:
Case 1: 3

Added by: hossamyosef
Added at: 2014-11-11 15:32:55 UTC
Time Limit: 2 seconds
Partial score: No
Source:ACM Jordanian Collegiate Programming Contest 2014