Suppose you are a professor who just moved to a new house. All your stuff is packed in wellidentified boxes, and a lot of them contain books of every kind and size. You just have chosen a room for your new library and you have unpacked all your books, but you are still missing the bookshelves. Now suppose you went to the hardware store and that they couldn’t offer you a full pre-built personal library, but only a series of identical rectangular bookshelves that can be stacked one over another, or placed next to each other. You have decided to go for this option, but you don’t know how many rectangular bookshelves are you going to need. The problem lies in all your personal rules to accommodate books in shelves. First, you don’t like to waste space or resources, so you want each bookshelf filled as much as possible, but using as few books as possible. Second, you don’t like to stack books over each other or occlude a book by putting another book in front of it. Third, you like your books placed vertically, in straight position, not with the front-cover facing the bottom or the top of the shelf, but facing either the left or the right side of the shelf. These are some of the things you need in your orderly life. Now, you want to know how to organize your books in the shelves, and since you don’t like to put books in front of others, you have decided to ignore the depth of the books and the shelves. Consequently, you have actually annotated the height and width of all your books. Given the height and width of an empty bookshelf, you can actually compute how much area of the shelf would each of your books take. This way you can also compute how much area of the shelf is being wasted when no more books fit in it. Then, given the number of bookshelves you are going to buy along with their height and width, you have decided to write a program that, for a given number of bookshelves, will compute the best way to organize your books in the shelves according to your personal rules, and report the total amount of space you are wasting among all shelves. Your plan is to input to this program several different number of shelves, with different sizes, and then decide what’s the best configuration for you to buy in the hardware store. Input The input can contain several problems. Each problem starts with four integers N, H, W, B, separated of each other by a blank space. 0 < N ≤ 10 represents the number of bookshelves you are going to buy. 0 < H,W ≤ 30 are the height and width of each bookshelf, respectively. 0 < B ≤ 100 represents the number of books you own. Then, B lines follow. Each of these lines contain two integers 0 < Bh, Bw ≤ 30 separated of each other by a blank space, representing the height and width of each book, respectively. Assume you measured your books while they were oriented vertically. This is how you want them to be placed in the shelves!. Their orientation must not be changed!. The end of input is represented by a case with N = 0, H = 0, W = 0, and B = 0. Output For each problem in the input, the output should be a single line containing an integer representing the total area of wasted space among all the bookshelves specified in the input problem. Sample Input 5542 46
2/2 54 1 10 10 3 10 10 10 10 10 10 3 10 10 3 10 10 10 10 10 11 0000 Sample Output 80 0 100