```go
package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	var n, m int
	fmt.Fscan(in, &n, &m)
	groups := make([][]int64, 4)
	for i := 0; i < n; i++ {
		var w int
		var c int64
		fmt.Fscan(in, &w, &c)
		groups[w] = append(groups[w], c)
	}
	type prefix struct {
		s   []int64
		num int
	}
	prefs := make([]prefix, 4)
	for w := 1; w <= 3; w++ {
		g := groups[w]
		sort.Slice(g, func(i, j int) bool { return g[i] > g[j] })
		nn := len(g)
		ss := make([]int64, nn+1)
		for i := 1; i <= nn; i++ {
			ss[i] = ss[i-1] + g[i-1]
		}
		prefs[w] = prefix{ss, nn}
	}
	const neginf int64 = -(1 << 60)
	dp := make([]int64, m+1)
	for i := range dp {
		dp[i] = neginf
	}
	dp[0] = 0
	for w := 1; w <= 3; w++ {
		pref := prefs[w]
		s := pref.s
		num := pref.num
		new_dp := make([]int64, m+1)
		for jj := range new_dp {
			new_dp[jj] = neginf
		}
		for r := 0; r < w; r++ {
			max_u := (m - r) / w
			q := make([]int64, max_u+1)
			for uu := 0; uu <= max_u; uu++ {
				jj := uu*w + r
				q[uu] = dp[jj]
			}
			temp := make([]int64, max_u+1)
			compute(0, max_u, 0, num, q, s, temp)
			for uu := 0; uu <= max_u; uu++ {
				jj := uu*w + r
				new_dp[jj] = temp[uu]
			}
		}
		dp = new_dp
	}
	var ans int64 = 0
	for j := 0; j <= m; j++ {
		if dp[j] > ans {
			ans = dp[j]
		}
	}
	fmt.Println(ans)
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func max(x, y int) int {
	if x > y {
		return x
	}
	return y
}

func compute(low, high, optlow, opthigh int, q, s, temp []int64) {
	if low > high {
		return
	}
	mid := (low + high) / 2
	const neginf int64 = -(1 << 60)
	var best int64 = neginf
	bestk := -1
	lft := max(optlow, 0)
	rgt := min(min(opthigh, mid), len(s)-1)
	for vv := lft; vv <= rgt; vv++ {
		ii := mid - vv
		if ii < 0 || ii >= len(q) {
			continue
		}
		val := q[ii] + s[vv]
		if val > best {
			best = val
			bestk = vv
		}
	}
	temp[mid] = best
	compute(low, mid-1, optlow, bestk, q, s, temp)
	compute(mid+1, high, bestk, opthigh, q, s, temp)
}
```