ACM ICPC Asia Manila 2009: Problem I

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-i.html


2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem I: ‘U Fill Me Up’
Input file: i.in
Output file: stdout
Execution time limit: 30 seconds

An n x m matrix can be filled by consecutive numbers starting from a number p, in a diagonal fashion starting at the upper right corner. For example, the 4 x 7 matrix below is filled up by numbers starting from 4.

(See Figure 1)

From the matrix, the sum of the elements covered by the region specified by indices (x1, y1) and (x2, y2) can be computed. For example, the sum of the elements covered by the region specified by index (1, 2) to index (2, 4) is 106 (because 21 + 14 + 13 + 23 + 20 + 15 = 106).

Input

The file consists of several test cases, each with a case number and the test case. A test case specifies the dimensions n and m of the matrix (where 0 <> 0, and x1 <= x2 and y1 <= y2). Output

For each test case, output the sum of the elements in the specified region.

Sample Input

Case 1: 4 7 4 1 2 2 4
Case 2: 4 7 4 3 6 4 7
Case 3: 4 7 4 5 2 6 8
Case 4: 4 7 4 4 7 5 10
Case 5: 8 5 1 2 1 2 5

Output for the Sample Input

Case 1: 106
Case 2: 47
Case 3: 0
Case 4: 10
Case 5: 48


(Acknowlegment: This problem was contributed by Dr. Nelson Marcos, De La Salle University - Manila)

.