시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 87 51 38 64.407%

문제

직교 좌표계에 존재하는 N개의 직사각형이 주어집니다. 주어진 N개의 직사각형은 중심은 모두 직교좌표계 가운데(원점)이며, 직사각형의 네 개의 변은 좌표축과 평행합니다. 각 사각형은 폭 (x 축을 따라)과 높이 (y 축을 따라)로 고유하게 식별됩니다. 아래 그림은 첫 번째 샘플 테스트를 보여줍니다.

디자인학부 학생인 미추홀 군은 각 사각형을 특정 색상으로 채색했으며, 이제는 종이의 채색된 부분의 면적(넓이)을 알고 싶어합니다. 즉, 미추홀 군은 적어도 하나의 직사각형에 속하는 영역(모든 직사각형의 합집합)의 면적을 알고 싶습니다.

입력

첫 번째 입력 줄에는 직사각형 수인 정수 N (1 ≤ N ≤ 1 000 000)이 주어집니다.

다음의 N 행에는 각각 해당 사각형의 크기가 너비(X) 와 높이 (Y)로 주어지며, X와 Y는 모두  짝수인 정수로 (2 ≤ X, Y ≤ 107)범위를 갖습니다.

출력

한줄로 색칠된 사각형의 합집합 영역의 넓이를 출력합니다.

예제 입력 1

3
8 2
4 4
2 6

예제 출력 1

28

예제 입력 2

5
2 10
4 4
2 2
8 8
6 6

예제 출력 2

68
W3sicHJvYmxlbV9pZCI6IjE0NDExIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkNTY5XHVjOWQxXHVkNTY5IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzFcdWFkNTAgXHVjODhjXHVkNDVjXHVhY2M0XHVjNWQwIFx1Yzg3NFx1YzdhY1x1ZDU1OFx1YjI5NCBOXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5ZDFcdWIyYzhcdWIyZTQuIFx1YzhmY1x1YzViNFx1YzljNCBOXHVhYzFjXHVjNzU4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWM5MTFcdWMyZWNcdWM3NDAgXHViYWE4XHViNDUwIFx1YzljMVx1YWQ1MFx1Yzg4Y1x1ZDQ1Y1x1YWNjNCBcdWFjMDBcdWM2YjRcdWIzNzAoXHVjNmQwXHVjODEwKVx1Yzc3NFx1YmE3MCwgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1YjEyNCBcdWFjMWNcdWM3NTggXHViY2MwXHVjNzQwIFx1Yzg4Y1x1ZDQ1Y1x1Y2Q5NVx1YWNmYyBcdWQzYzlcdWQ1ODlcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWMwMSBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHVkM2VkICh4IFx1Y2Q5NVx1Yzc0NCBcdWI1MzBcdWI3N2MpXHVhY2ZjIFx1YjE5Mlx1Yzc3NCAoeSBcdWNkOTVcdWM3NDQgXHViNTMwXHViNzdjKVx1Yjg1YyBcdWFjZTBcdWM3MjBcdWQ1NThcdWFjOGMgXHVjMmRkXHViY2M0XHViNDI5XHViMmM4XHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVjMGQ4XHVkNTBjIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Yjk3YyBcdWJjZjRcdWM1ZWNcdWM5MGRcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL29ubGluZWp1ZGdlaW1hZ2VzLnMzLmFtYXpvbmF3cy5jb21cL3Byb2JsZW1cLzE0NDExXC8lRUMlOEElQTQlRUQlODElQUMlRUIlQTYlQjAlRUMlODMlQjclMjAyMDE3LTAyLTAyJTIwJUVDJTk4JUE0JUVEJTlCJTg0JTIwOC4xNS40MS5wbmdcIiBzdHlsZT1cImhlaWdodDozMTZweDsgd2lkdGg6MzgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHAgZGlyPVwibHRyXCI+XHViNTE0XHVjNzkwXHVjNzc4XHVkNTU5XHViZDgwIFx1ZDU1OVx1YzBkZFx1Yzc3OCBcdWJiZjhcdWNkOTRcdWQ2NDAgXHVhZDcwXHVjNzQwIFx1YWMwMSBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVkMmI5XHVjODE1IFx1YzBjOVx1YzBjMVx1YzczY1x1Yjg1YyBcdWNjNDRcdWMwYzlcdWQ1ODhcdWM3M2NcdWJhNzAsIFx1Yzc3NFx1YzgxY1x1YjI5NCBcdWM4ODVcdWM3NzRcdWM3NTggXHVjYzQ0XHVjMGM5XHViNDFjIFx1YmQ4MFx1YmQ4NFx1Yzc1OCBcdWJhNzRcdWM4MDEoXHViMTEzXHVjNzc0KVx1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjMmY2XHVjNWI0XHVkNTY5XHViMmM4XHViMmU0LiBcdWM5ODksIFx1YmJmOFx1Y2Q5NFx1ZDY0MCBcdWFkNzBcdWM3NDAgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM1ZDAgXHVjMThkXHVkNTU4XHViMjk0IFx1YzYwMVx1YzVlZChcdWJhYThcdWI0ZTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDU2OVx1YzlkMVx1ZDU2OSlcdWM3NTggXHViYTc0XHVjODAxXHVjNzQ0IFx1YzU0Y1x1YWNlMCBcdWMyZjZcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cCBkaXI9XCJsdHJcIj5cdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzc4NVx1YjgyNSBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YzIxOFx1Yzc3OCBcdWM4MTVcdWMyMTggTiAoMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjXHVjNzU4IE4gXHVkNTg5XHVjNWQwXHViMjk0IFx1YWMwMVx1YWMwMSBcdWQ1NzRcdWIyZjkgXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YWMwMCBcdWIxMDhcdWJlNDQoWCkgXHVjNjQwIFx1YjE5Mlx1Yzc3NCAoWSlcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBYXHVjNjQwIFlcdWIyOTQgXHViYWE4XHViNDUwICZuYnNwO1x1YzlkZFx1YzIxOFx1Yzc3OCBcdWM4MTVcdWMyMThcdWI4NWMgKDIgJmxlOyBYLCBZICZsZTsgMTA8c3VwPjc8XC9zdXA+KVx1YmM5NFx1YzcwNFx1Yjk3YyBcdWFjMTZcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVkNTVjXHVjOTA0XHViODVjIFx1YzBjOVx1Y2U2MFx1YjQxYyBcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NTggXHVkNTY5XHVjOWQxXHVkNTY5IFx1YzYwMVx1YzVlZFx1Yzc1OCBcdWIxMTNcdWM3NzRcdWI5N2MgXHVjZDljXHViODI1XHVkNTY5XHViMmM4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjE0NDExIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVW5pamEiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gTiByZWN0YW5nbGVzLCB3aGljaCBhcmUgY2VudGVyZWQgaW4gdGhlIGNlbnRlciBvZiB0aGUgQ2FydGVzaWFuIGNvb3JkaW5hdGUgc3lzdGVtIGFuZCB0aGVpciBzaWRlcyBhcmUgcGFyYWxsZWwgdG8gdGhlIGNvb3JkaW5hdGUgYXhlcy4gRWFjaCByZWN0YW5nbGUgaXMgdW5pcXVlbHkgaWRlbnRpZmllZCB3aXRoIGl0cyB3aWR0aCAoYWxvbmcgdGhlIHgtYXhpcykgYW5kIGhlaWdodCAoYWxvbmcgdGhlIHktYXhpcykuIFRoZSBsb3dlciBpbWFnZSBkZXBpY3RzIHRoZSBmaXJzdCBzYW1wbGUgdGVzdC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvb25saW5lanVkZ2VpbWFnZXMuczMuYW1hem9uYXdzLmNvbVwvcHJvYmxlbVwvMTQ0MTFcLyVFQyU4QSVBNCVFRCU4MSVBQyVFQiVBNiVCMCVFQyU4MyVCNyUyMDIwMTctMDItMDIlMjAlRUMlOTglQTQlRUQlOUIlODQlMjA4LjE1LjQxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjMxNnB4OyB3aWR0aDozODBweFwiIFwvPjxcL3A+XHJcblxyXG48cD5NaXJrbyBoYXMgY29sb3VyZWQgZWFjaCByZWN0YW5nbGUgaW4gYSBjZXJ0YWluIGNvbG9yIGFuZCBub3cgd2FudHMgdG8ga25vdyB0aGUgYXJlYSBvZiB0aGUgY29sb3VyZWQgcGFydCBvZiB0aGUgcGFwZXIuIEluIG90aGVyIHdvcmRzLCBoZSB3YW50cyB0byBrbm93IHRoZSBudW1iZXIgb2YgdW5pdCBzcXVhcmVzIHRoYSB0IGJlbG9uZyB0byBhdCBsZWFzdCBvbmUgcmVjdGFuZ2xlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAxIDAwMCAwMDApLCB0aGUgbnVtYmVyIG9mIHJlY3RhbmdsZXMuPFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIGV2ZW4gaW50ZWdlcnMgWCBhbmQgWSAoMiAmbGU7IFgsIFkgJmxlOyAxMDxzdXA+NzxcL3N1cD4pLCBkaW1lbnNpb25zICh3aWR0aCBhbmQgaGVpZ2h0LCByZXNwZWN0aXZlbHkpIG9mIHRoZSBjb3JyZXNwb25kaW5nIHJlY3RhbmdsZXMuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgYXJlYS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=