사탕 배달

사탕을 좋아하는 아기 석환은 집에 N개의 사탕이 든 자루를 들여놓았다. 자루에는 두 종류의 사탕이 있는데, 작은 사탕은 3g, 큰 사탕은 5g의 무게를 가진다. 똑똑한 아기 석환은 자루에 있는 모든 사탕에 대해 그 사탕의 당도 s_i를 계산해 두었다. s_i는 양의 정수이고, s_i가 클수록 사탕이 달콤하다.

shake! 2019 대회에 참가하려고 짐을 싸는 아기 석환은 달콤한 사탕을 최대한 많이 담아가서 대회 도중 당분을 보충하려고 한다. 하지만 연약한 아기 석환은 가방에 최대 wg(w그램)의 사탕만 담을 수 있다. 아기 석환이 이 조건을 만족하도록 사탕을 담았을 때, 담아간 사탕의 당도 합은 최대 얼마가 될 수 있을까?

첫 번째 줄에 사탕의 개수 N(1 ≤ N ≤ 250,000)과 무게 제한 w(0 ≤ w ≤ 5N)가 주어진다.

이후 N개의 줄에 각 사탕의 종류 t_i, 당도 s_i가 주어진다. ($t_i \in \{3, 5\}$, 1 ≤ s_i ≤ 10^9)

아기 석환이 조건을 만족하도록 담아갈 수 있는 사탕의 당도 합의 최댓값을 출력하라.

Java/Kotlin 사용자를 위한 경고! 일반적인 상식과 달리, Java의 Arrays.sort 내장 함수와 Kotlin의 IntArray.sort()는 $O(N^2)$ 시간 복잡도의 알고리즘으로 구현되어 있다. 이 문제의 테스트 데이터는 그 함수를 사용했을 때 시간 초과가 나도록 설계되었으니, Collections.sort 같은 다른 정렬 함수를 사용하라.