跳到主要内容
图灵 OJTURING / ONLINE JUDGE

#F0796. Beautiful fountains rows

  • ID: 802
  • 传统题
  • 2000ms
  • 256MiB
  • 尝试: 0
  • AC · 已通过: 0
  • 教学难度:挑战
  • 上传者:
  • 数据结构
  • 挑战
  • 难度
  • 共享题库
  • Codeforces
  • 英文题面
  • 题目来源
  • 题面语言

Beautiful fountains rows

题目描述

F. Beautiful fountains rows
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Butler Ostin wants to show Arkady that rows of odd number of fountains are beautiful, while rows of even number of fountains are not.

The butler wants to show Arkady n gardens. Each garden is a row of m cells, the i-th garden has one fountain in each of the cells between li and ri inclusive, and there are no more fountains in that garden. The issue is that some of the gardens contain even number of fountains, it is wrong to show them to Arkady.

Ostin wants to choose two integers a≤b and show only part of each of the gardens that starts at cell a and ends at cell b. Of course, only such segments suit Ostin that each garden has either zero or odd number of fountains on this segment. Also, it is necessary that at least one garden has at least one fountain on the segment from a to b.

Help Ostin to find the total length of all such segments, i.e. sum up the value (b-a+1) for each suitable pair (a,b).

Input

The first line contains two integers n and m (1≤n,m≤2·105)− the number of gardens and the length of each garden.

n lines follow. The i-th of these lines contains two integers li and ri (1≤li≤ri≤m)− the bounds of the segment that contains fountains in the i-th garden.

Output

Print one integer: the total length of all suitable segments.

Examples
Input
1 5
2 4
Output
23
Input
3 6
2 4
3 6
4 4
Output
19
Note

In the first example the following pairs suit Ostin: (a,b): (1,2), (1,4), (1,5), (2,2), (2,4), (2,5), (3,3), (4,4), (4,5).

In the second example the following pairs suit Ostin: (a,b): (1,2), (1,5), (2,2), (2,5), (3,3), (4,4), (4,6), (5,5), (6,6).


题目来源:fps-www.educg.net-codeforce-1-2833.xml.zip;FPS 共享题包,题包内第 224 题。保留原作者与原赛事署名。