After receiving the lamp, Aladdin and Abu are on their way to get out from the cave when they found a statue of Sir Hussain, one of the most powerful Royal General to walk on Earth. Below the statue is written a real life problem that Sir Hussain solved and in order to get out of the cave one must solve this riddle. Aladdin out of options starts reading the riddle- Once upon a time in the Kingdom far far away lived Sir Hussain, the chief Royal General. He was very proud of his men and he liked to invite the King to come and watch drill exer- cises which demonstrated the fighting techniques and tactics of the squad he was in charge of. But time went by and one-day Sir Hussain had a major argument with an old witch (there were rumours that the argument occurred after the general spoke badly of the witch flying techniques. That seemed to hurt the old witch very deeply). As the result of the argument, the witch put a rather strange curse upon the general. It sounded all complicated and quite harmless: "If the squared distance between some two soldiers equals to 5, then those soldiers will conflict with each other!" The drill exercises are held on a rectangular n × m field, split into nm square 1 × 1 segments for each soldier. Thus, the square of the distance between the soldiers that stand on squares (x_(1), y_(1)) and (x_(1),y_(2)) equals exactly (x_(1)-x_(2))^(2)+(y_(1)-y_(2))^(2) . Now not all nm squad soldiers can partici- pate in the drill exercises as it was before the old witch curse. Unless, of course, the general wants the soldiers to fight with each other or even worse. For example, if he puts a soldier in the square (2, 2), then he cannot put soldiers in the squares (1, 4), (3, 4), (4, 1) and (4, 3) — each of them will conflict with the soldier in the square (2, 2). Find the sum of maximum number of soldiers that can be simultaneously positioned on this field for each of the following cases i) 1002 2 ii) 451 2 iii) 780 2 iv) 121 2
