// https://leetcode.com/problems/find-the-minimum-amount-of-time-to-brew-potions/description/?envType=company&envId=google&favoriteSlug=google-thirty-days

class Solution {
    private boolean isValid(int potionIdx, long startTime, int n, int m, long[] prevEndTime, int[] skill, int[] mana, long[] newEndTime) {
        if (startTime < prevEndTime[0]) {
            return false;
        }

        newEndTime[0] = startTime + ((long) skill[0] * mana[potionIdx]);

        for (int i = 1; i < n; i++) {
            long newStartTimeForIthWizard = newEndTime[i - 1];
            if (newStartTimeForIthWizard < prevEndTime[i]) {
                return false;
            } else {
                newEndTime[i] = newStartTimeForIthWizard + ((long) skill[i] * mana[potionIdx]);
            }
        }

        return true;
    }

    public long minTime(int[] skill, int[] mana) {
        int n = skill.length; // #wizards
        int m = mana.length; // #potions

        long[] endTime = new long[n];

        // for 0th potion, time taken by all n wizards
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                endTime[i] = ((long) skill[i] * mana[0]);
            } else {
                endTime[i] = endTime[i - 1] + ((long) skill[i] * mana[0]);
            }
        }

        for (int potion = 1; potion < m; potion++) {
            long L = endTime[0], R = endTime[n - 1];
            long[] newTentativeEndTime = new long[n];

            boolean isValidFound = false;

            while (L <= R) {
                long mid = L + ((R - L) >> 1L);

                if (isValid(potion, mid, n, m, endTime, skill, mana, newTentativeEndTime)) {
                    isValidFound = true;
                    R = mid - 1;
                } else {
                    L = mid + 1;
                }
            }

            if (isValidFound) {
                endTime = newTentativeEndTime;
            }
        }

        return endTime[n - 1];
    }
}