import kotlin.math.min private var L: Long = 0 private var a: ArrayList = ArrayList() private var b: ArrayList = ArrayList() private var A = 0 private var B = 0 private var dp: Array> = Array(0) { Array(0) { LongArray(0) } } fun main() { val (n, L2) = readln().split(" ").map { it.toLong() } L = L2 a.add(-1L) b.add(-1L) for (i in 0 until n) { val (c, t) = readln().split(" ") (if (c == "N") a else b).add(t.toLong()) } A = a.size B = b.size val INF = 1L shl 60 dp = Array(2) { Array(A + 1) { LongArray(B + 1) } } for (i in 0..1) { for (j in 0..A) { java.util.Arrays.fill(dp[i][j], INF) } } dp[0][1][0] = 0 dp[1][0][1] = 0 for (i in 0 until A) { for (j in 0 until B) { if (i > 0 && dp[0][i][j] < INF) { chain(0, i, j, a.get(i), dp[0][i][j]) } if (j > 0 && dp[1][i][j] < INF) { chain(1, i, j, b.get(j), dp[1][i][j]) } } } println(min(dp[0][A][B - 1], dp[1][A - 1][B])) } fun chain(k: Int, i: Int, j: Int, t: Long, cost: Long) { var i = i var j = j var cost = cost if (k == 0) { while (i + 1 < A && a[i + 1] <= t) { cost += t - a[i] i += 1 } if (a[i] > t) { dp[k][i][j] = min(dp[k][i][j], cost) return } cost += t - a[i] dp[k][i + 1][j] = min(dp[k][i + 1][j], cost) if (j + 1 < B) { chain(1 - k, i, j + 1, t + L, cost) } } else { while (j + 1 < B && b[j + 1] <= t) { cost += t - b[j] j += 1 } if (b[j] > t) { dp[k][i][j] = min(dp[k][i][j], cost) return } cost += t - b[j] dp[k][i][j + 1] = min(dp[k][i][j + 1], cost) if (i + 1 < A) { chain(1 - k, i + 1, j, t + L, cost) } } }