ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

USU Internal Contest March'2001

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Tmutarakan Exams

Time limit: 1.0 second
Memory limit: 64 MB
University of New Tmutarakan trains the first-class specialists in mental arithmetic. To enter the University you should master arithmetic perfectly. One of the entrance exams at the Divisibility Department is the following. Examinees are asked to find K different positive integers that have a common divisor greater than one. All integers in this set should not exceed S. The numbers K and S are announced at the beginning of the exam. To exclude copying (the Department is the most prestigious in the town!) each set of numbers is credited only once (to the person who submitted it first).
Last year these numbers were K = 25 and S = 49 and, unfortunately, nobody passed the exam. Moreover, it was proved later by the best minds of the Department that there do not exist sets of numbers with the required properties. To avoid embarrassment this year, the dean asked for your help. You should find the number of sets of K different positive integers, each of the integers not exceeding S, which have a common divisor greater than one. Of course, the number of such sets equals the maximal possible number of new students of the Department.


The only line contains integers K and S (2 ≤ KS ≤ 50).


Output the maximal possible number of the Department's new students if this number does not exceed 10000 which is the maximal capacity of the Department, otherwise you should output 10000.


3 10


In the example the following sets satisfy the conditions:
  1. (2, 4, 6);
  2. (2, 4, 8);
  3. (2, 4, 10);
  4. (2, 6, 8);
  5. (2, 6, 10);
  6. (2, 8, 10);
  7. (3, 6, 9);
  8. (4, 6, 8);
  9. (4, 6, 10);
  10. (4, 8, 10);
  11. (6, 8, 10).
Problem Author: Stanislav Vasilyev
Problem Source: USU Open Collegiate Programming Contest March'2001 Senior Session
To submit the solution for this problem go to the Problem set: 1091. Tmutarakan Exams