class Solution:

    def minimumCost(self, cost: List[int]) -> int:

        return sum(x for i, x in enumerate(sorted(cost, reverse=True)) if (i + 1) % 3 != 0)

class Solution:

    def numberOfArrays(self, differences: List[int], lower: int, upper: int) -> int:

        nums = list(accumulate(differences, initial=0))

        return max((upper - lower) - (max(nums) - min(nums)) + 1, 0)

class Solution:

    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:

        m, n = len(grid), len(grid[0])

        sr, sc = start

        low, high = pricing

        ans = []

        deq = deque([[sr, sc, 0]])

        visited = [[False] * n for _ in range(m)]

        while deq:

            r, c, d = deq.popleft()

            if visited[r][c]: continue

            visited[r][c] = True

            nxts = [[a, b, d+1] for a, b in [[r-1, c], [r+1, c], [r, c-1], [r, c+1]] if 0 <= a < m and 0 <= b < n and grid[a][b] >= 1 and not visited[a][b]]

            if low <= grid[r][c] <= high: ans.append([r, c, d])

            deq.extend(nxts)

        return [[a, b] for a, b, c in sorted(ans, key=lambda x: (x[2], grid[x[0]][x[1]], x[0], x[1]))[:k]]

class Solution:

    def numberOfWays(self, corridor: str) -> int:

        a = [i for i, c in enumerate(corridor) if c == 'S']

        ans = 1

        for i in range(1, len(a) - 1, 2):

            ans = (ans * (a[i+1] - a[i])) % int(1e9 + 7)

        return ans * (len(a) % 2 == 0 and len(a) >= 2)