class Solution:

    def divideString(self, s: str, k: int, fill: str) -> List[str]:

        n = len(s)

        ans = []

        for i in range(n // k + 1):

            ans.append(s[i*k:(i+1)*k])

        if len(ans[-1]) == 0:

            ans.pop()

        if len(ans[-1]) != k:

            ans[-1] = ans[-1] + fill * (k - len(ans[-1]))

        return ans

class Solution:

    def minMoves(self, target: int, maxDoubles: int) -> int:

        inc = 0

        dou = 0

        while target != 1:

            if target % 2 == 1:

                inc += 1

                target -= 1

            else:

                if dou < maxDoubles:

                    dou += 1

                    target //= 2

                else:

                    inc += target - 1

                    target = 1

        return inc + dou

class Solution:

    def mostPoints(self, questions: List[List[int]]) -> int:

        n = len(questions)

        ans = 0

        dp = [0] * n

        for i, (p, b) in enumerate(questions):

            ans = max(ans, dp[i] + p)

            dp[i] = ans

            if i + b + 1 < n:

                dp[i + b + 1] = max(dp[i + b + 1], ans)

        return ans

class Solution:

    def mostPoints(self, questions: List[List[int]]) -> int:

        n = len(questions)

        dp = [0] * (n + 1)

        for i in range(n - 1, -1, -1):

            p, b = questions[i]

            j = i + b + 1

            dp[i] = max(dp[i + 1], p + (dp[j] if j < n else 0))

        return dp[0]

class Solution:

    def mostPoints(self, questions: List[List[int]]) -> int:

        n = len(questions)

        dp = [0] * (n + 1)

        for i, (p, b) in enumerate(questions):

            dp[i + 1] = max(dp[i + 1], dp[i])

            j = min(i + b + 1, n)

            dp[j] = max(dp[j], dp[i] + p)

        return dp[n]

class Solution:

    def maxRunTime(self, n: int, batteries: List[int]) -> int:

        l, r = 0, sum(batteries) // n

        while l < r:

            x = (l + r + 1) // 2

            if n * x <= sum(min(b, x) for b in batteries): l = x

            else: r = x - 1

        return l

class Solution:

    def maxRunTime(self, n: int, batteries: List[int]) -> int:

        batteries.sort(reverse=True)

        s = sum(batteries)

        for b in batteries:

            if b <= s // n: return s // n

            s -= b

            n -= 1