18234번 - 당근 훔쳐 먹기

꽉꽉나라의 농부 오리는 아무것도 심어져 있지 않은 텃밭을 하나 가지고 있다. 오리는 그 텃밭에 N종류의 당근을 하나씩 심고 T일 동안 재배할 예정이다.

당근 i(1 ≤ i ≤ N)는 처음에는 w_i의 맛을 가지고 있고, 각 당근 i에 사용할 p_i만큼 맛을 증가시켜주는 영양제가 당근 종류별로 T개씩 준비되어 있다. 오리는 당근이 본래의 맛보다 훨씬 맛있어지기를 바라기 때문에 p_i는 항상 w_i이상의 값을 가지도록 준비했다. 잠이 많은 오리는 매일 오전에만 텃밭에 나와 당근들을 관리한다. 오리는 각 당근 i에 대해 당근 i가 자리에 없다면 당근 i를 심고, 그렇지 않다면 당근 i에 영양제를 하나 준다.

꽉꽉나라에 놀러 온 토끼는 오리가 오전에만 당근을 관리한다는 사실을 알고 오리의 텃밭을 찾아가 당근을 훔쳐 먹을 계획을 세웠다. 토끼는 위장이 작아서 하루에 최대 하나의 당근을 먹을 수 있고 당근을 먹지 않을 수도 있다. 또한 당근 하나를 먹기로 마음먹으면 남기지 않고 먹으며, 오리와 마주치지 않기 위해 오후에만 텃밭에 찾아간다. 토끼는 자신이 먹은 당근의 맛의 합을 최대로 하고 싶어 한다.

T일 동안 토끼가 먹을 수 있는 당근의 맛의 합의 최댓값을 구해보자.

첫 번째 줄에 N(1 ≤ N ≤ 200,000)과 T(N ≤ T ≤ 100,000,000)가 공백으로 구분되어 주어진다. 오리는 당근의 맛을 충분히 높이기 위해 항상 N이상인 T일 동안 재배한다.

다음 N개의 줄에 걸쳐서 i+1번째 줄에 당근 i의 w_i와 p_i가 공백으로 구분되어 주어진다. (1 ≤ i ≤ N, 1 ≤ w_i ≤ p_i ≤ 100, w_i와 p_i는 정수)

첫 번째 줄에 토끼가 T일 동안 먹을 수 있는 당근의 맛의 합의 최댓값을 출력한다. 정답은 32비트 정수 변수(int) 범위를 초과할 수 있기 때문에 64비트 정수 변수(C/C++ : long long, JAVA : long)를 사용해야 한다.