package main

type Queue interface {
	Enqueue(value int)
	Dequeue() int
	Peek() int
	IsEmpty() bool
}

type MonoDecQueue struct {
	elements []int
}

func NewMonoDecQueue() *MonoDecQueue {
	return &MonoDecQueue{elements: make([]int, 0)}
}

func (q *MonoDecQueue) Enqueue(value int) {
	for !q.IsEmpty() && q.elements[len(q.elements)-1] < value {
		q.elements = q.elements[:len(q.elements)-1]
	}
	q.elements = append(q.elements, value)
}

func (q *MonoDecQueue) Dequeue() int {
	if q.IsEmpty() {
		panic("queue is empty")
	}
	value := q.elements[0]
	q.elements = q.elements[1:]
	return value
}

func (q *MonoDecQueue) Peek() int {
	if q.IsEmpty() {
		panic("queue is empty")
	}
	return q.elements[0]
}

func (q *MonoDecQueue) IsEmpty() bool {
	return len(q.elements) == 0
}

func MaximumRobots(chargeTimes []int, runningCosts []int, budget int64) int {
	l := len(chargeTimes)
	if l != len(runningCosts) {
		return 0
	}

	j := 0
	prevJ := -1
	s := 0
	maxRobots := 0

	q := NewMonoDecQueue()

	for i := 0; i < l; i++ {

		if j < i {
			j = i
		}

		for ; j < l; j++ {
			num := j - i + 1
			if prevJ != j {
				s += runningCosts[j]
				q.Enqueue(chargeTimes[j])
			}

			prevJ = j
			if int64(s*num+q.Peek()) <= budget {
				if maxRobots <= num {
					maxRobots = num
				}
			} else {
				break
			}
		}

		if !q.IsEmpty() {
			if q.Peek() == chargeTimes[i] {
				q.Dequeue()
			}
		}

		s -= runningCosts[i]
	}

	return maxRobots
}

func MaximumRobotsEx(chargeTimes []int, runningCosts []int, budget int64) int {
	l := len(chargeTimes)
	if l != len(runningCosts) {
		return 0
	}

	prevCharges := make([]int, l)
	prevCosts := make([]int, l)
	maxWndRobots := make([]int, l+1)

	maxRobots := 0

	for wnd := 1; wnd <= l; wnd++ {
		windows := l - wnd + 1

		begin := 0
		end := wnd - 1
		w := 0
		for w = 0; w < windows; w++ {
			m := chargeTimes[end]

			if m > prevCharges[w] {
				prevCharges[w] = m
			}
			prevCosts[w] += runningCosts[end]

			totalCost := int64(wnd*prevCosts[w] + prevCharges[w])
			if totalCost <= budget {
				maxRobots = wnd
			}

			begin++
			end++
		}

		maxWndRobots[wnd] = maxRobots
		if maxWndRobots[wnd] == maxWndRobots[wnd-1] {
			break
		}
	}

	return maxRobots
}