{"raw_statement":[{"iden":"statement","content":"A team contest with a new format is going to be held on BruteForces: all tests are open, and a team may consist of any number of people. The final rating change is, of course, evenly distributed among the team members.\n\nOn the very first contest the following non-trivial problem was given:\n\n«A table $S$ of size $m times n$ is given. In the cell $S_{i , j}$ (where $1 <=.slant i <=.slant m, 1 <=.slant j <=.slant n$) the sum of all integers from $1$ to $i + j$ is written. Find the sum of all numbers in the sub-table with corner cells $S_{1 , 1}$ and $S_{a , b}$ for the given $a, b$.»\n\nA total of $T$ tests were prepared for this problem.\n\nShortly after reading the problem statement, blue coder Vasya came up with a solution: if only we knew the numbers in all cells, then we could just use the regular Fenwick tree!\n\nIt is enough for Vasya to compute the numbers in some of the cells, not necessarily all. In order to do so, he decided to invite some green coders to his team, and ask each of them to calculate the number in a cell $S_{i , j}$ (one green coder will be assigned to exactly one cell). Since the final rating change is evenly distributed among the team members, Vasya wants to invite as few coders as possible. Thus, he wants to compute the numbers in only those cells that are necessary for answering at least one test (i. e. those cells that lie in at least one sub-table). \n\nWhat is the minimal number of coders that Vasya has to invite to his team so as to accomplish his goal?\n\nIn the first line there are two integers, $m$ and $n$, that describe the size of the table.\n\nIn the second line there is $T$, the number of tests.\n\nOn each of the following $T$ lines, there are numbers $a, b$ — coordinates of one of the corners of the sub-tables.\n\n$1 <=.slant m, n <=.slant 5000$\n\n$1 <=.slant T <=.slant 1000$\n\n$1 <=.slant a <=.slant m$\n\n$1 <=.slant b <=.slant n$\n\nOne integer — the minimal number of green coders that Vasya has to invite to his team.\n\n"},{"iden":"input","content":"In the first line there are two integers, $m$ and $n$, that describe the size of the table.In the second line there is $T$, the number of tests.On each of the following $T$ lines, there are numbers $a, b$ — coordinates of one of the corners of the sub-tables.$1 <=.slant m, n <=.slant 5000$$1 <=.slant T <=.slant 1000$$1 <=.slant a <=.slant m$$1 <=.slant b <=.slant n$"},{"iden":"output","content":"One integer — the minimal number of green coders that Vasya has to invite to his team."},{"iden":"examples","content":"Input4 4\n3\n1 3\n2 2\n4 1\nOutput7\nInput5 5\n5\n3 2\n2 1\n4 4\n3 5\n2 4\nOutput19\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"Let $ m, n \\in \\mathbb{Z}^+ $ be the dimensions of the table $ S $.\n\nLet $ T \\in \\mathbb{Z}^+ $ be the number of test cases.\n\nFor each test case $ k \\in \\{1, \\dots, T\\} $, let $ (a_k, b_k) \\in \\{1, \\dots, m\\} \\times \\{1, \\dots, n\\} $ define the bottom-right corner of a sub-table with top-left corner $ (1,1) $.\n\nDefine the set of required cells:\n$$\nR = \\bigcup_{k=1}^{T} \\left( \\{1, \\dots, a_k\\} \\times \\{1, \\dots, b_k\\} \\right)\n$$\n\n**Objective**: Compute $ |R| $, the cardinality of the union of all rectangular sub-tables from $ (1,1) $ to $ (a_k, b_k) $ for $ k = 1, \\dots, T $.","simple_statement":"Find the minimum number of cells in an m×n table that must be computed so that, for each of T given sub-tables (from (1,1) to (a,b)), all cells inside it are covered. Each computed cell can be used for multiple sub-tables.","has_page_source":false}