Diego and Hammer Game
By Gustavo Ribeiro, IFPB - Campina Grande 
Brazil
By Gustavo Ribeiro, IFPB - Campina Grande Brazil
During the patron saint party of Lagoa de Roça, there are different games, toys and amusement parks settle in the downtown of this small city of Paraíba. One of them, it’s the not so popular Hammer Game. The game consists of a bumpy board and a hammer which fully covers the board. Besides, there are small creatures (puppets) that occasionally come out of the board holes, are visible for a second and then return to hide in the hole. The aim of the Hammer Game is to hit the largest number of creatures with at most m hammerings.
After staying a while watching the game, Diego realized that each of the creatures had an apparition pattern, in other words, if a certain creature i first appear at the moment di, it will appear again at the moment 2di, at the moment 3di and so on until the moment kdi arrives. After that the creature doesn’t appear anymore. Diego noted the moment of the first and the last apparition of each creature, now he needs your help. Write a program that with these informations and the number m of available hammerings, report the maximum amount of creatures that can be hammered.
Obs.: When a creature is hammered, it no longer appears during the game.
The first line of the input will contain two integers, 1 ≤ n ≤ 103 e 1 ≤ m ≤ 10, the number of creatures and the number of available hammerings. Each of the next n lines will contain two integers 2 ≤ di ≤ 500 e 2 ≤ kdi ≤ 103, the moment of the first and last appariton of the ith-creature, respectively. It is guaranteed that di ≤ kdi.
Print the maximum amount of creatures that can be hammered with at most m hammerings.
| Input Samples | Output Samples |
|
3 2 2 4 4 16 16 32 |
3 |
|
4 1 5 25 2 10 3 9 12 24 |
2 |