Knights Roaming

Consider an infinite Chessboard. As the chessboard is infinite, each of its cells is denoted by two integers (x,y). There are N knights in this chessboard. Each of these Knights can go certain steps. So, each knight covers a certain part of the chessboard. It is possible that, one cell can be covered by more than one knight. Even, two knights can be in the same position of the board. You all know that a knight at (x,y) can go to (x±2,y±1) and (x±1,y±2) in next step. In this problem, you will be given the description of N knights (its initial position and the steps it can travel at most). You have to find the number of distinct cells covered by the N knights. Input Each input set starts with N (1 ≤ N ≤ 30) denoting the number of knights. In next few lines the position (x, y) and the maximum number of steps k (0 ≤ k ≤ 50) of N knights will be given. The value of x, y will be in the range −109 to +109. Input is terminated by N = 0. There will be at most 50 test cases. There is a blank line between two consecutive sets. Output For each test case, print in a line the number of distinct cells, which can be traversed by any of N knights. Sample Input 5 110 220 330 440 550 5 111 221 331 441 551 4 -1 1 2 221 333 443 0

2/2 Sample Output 5 33 149