굶은 곰 (Hungry Cow) 1s 32MB

문제

굶은 곰은 저녁 시간마다 창고에 젤리가 있을 경우 하나씩 꺼내 먹는다.

사육사는 곰이 굶주린 모습을 보기 싫어하기에 종종 아침에 젤리를 창고에 넣는다.

정확히는 d_i일 차의 아침에 b_i개의 젤리를 창고에 넣는다. (1 \le d_i \le 10^{14}, \; 1 \le b_i \le 10^9)

첫 T일 동안 곰이 먹게 되는 젤리의 수를 계산하라.

첫 번째 줄에 N과 T가 주어진다. (1 \le N \le 10^5, \; 1 \le T \le 10^{14})

그 다음 N줄에 걸쳐 d_i와 b_i가 주어진다. (1 \le d_1 \lt d_2 \lt \cdots \lt d_N \le T)

첫 T일 동안 곰이 먹게 되는 젤리의 수를 출력한다.

수가 커질 수 있으므로 64bit 자료형을 써야 할 수 있다.

1space_bar 5
keyboard_return
1space_bar 2

2개의 젤리가 1일 차 아침에 도착한다.

곰은 1일 차에 1개의 젤리를 먹고 2일 차에 1개의 젤리를 먹는다. 3~5일 차에는 먹을 젤리가 없다.

따라서 곰은 2개의 젤리를 5일 동안 먹는다.

2space_bar 5
keyboard_return
1space_bar 2
keyboard_return
5space_bar 10

2개의 젤리가 1일 차 아침에 도착한다.

곰은 1일 차와 2일 차에 젤리를 먹는다.

3일 차와 4일 차에는 먹을 젤리가 없다. 5일 차 아침에 10개의 젤리가 도착한다.

곰은 5일 차 저녁에 하나의 젤리를 먹는다.

따라서 곰은 3개의 젤리를 5일 동안 먹는다.

2space_bar 5
keyboard_return
1space_bar 10
keyboard_return
5space_bar 10

10개의 젤리가 1일 차 아침에 도착한다.

곰은 1~4일 차에 젤리를 1개 씩 먹는다.

5일 차 아침에 10개의 젤리가 도착한다. 따라서 16개의 젤리가 남아 있다.

5일 차 저녁에 곰은 젤리를 먹는다.

따라서 곰은 5개의 젤리를 5일 동안 먹는다.

USACO 2023 February Bronze

로그인해야 코드를 작성할 수 있어요.