func purchasePlans(nums []int, target int) int {
    sort.Ints(nums)
    ans := 0
    i, j := 0, len(nums)-1
    for; i < j; i++ {
        for i<j && nums[i]+nums[j]>target {
            j--
        }
        ans += j - i

    }
    return ans % (1e9 + 7)
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func orchestraLayout(num int, xPos int, yPos int) int {
    qx := min(num-xPos-1, xPos)
    qy := min(num-yPos-1, yPos)
    q := min(qx, qy)
    n1 := num*4 - 4
    var start int
    if q == 0 {
        start = 1
    } else {
        start = n1*q - (q-1)*q*4 + 1
    }
    if xPos == q {
        start += yPos - xPos
    } else if yPos == q {
        start += (num-q*2-1)*3 + num - q - 1 - xPos
    } else if num-xPos-1 == q {
        start += (num-q*2-1)*2 + num - q - 1 - yPos
    } else if num-yPos-1 == q {
        start += num - q*2 - 1 + xPos - q
    }
    if start%9 == 0 {
        return 9
    }
    return start % 9
}

type myHeap struct {
	arr []int
}

func (m *myHeap) Len() int {
	return len(m.arr)
}

func (m *myHeap) Less(i, j int) bool {
	return m.arr[i] > m.arr[j]
}

func (m *myHeap) Swap(i, j int) {
	m.arr[i], m.arr[j] = m.arr[j], m.arr[i]
}

func (m *myHeap) Push(x interface{}) {
	m.arr = append(m.arr, x.(int))
}

func (m *myHeap) Pop() interface{} {
	top := m.arr[len(m.arr)-1]
	m.arr = m.arr[:len(m.arr)-1]
	return top
}
func magicTower(nums []int) int {
	rest := 0
	mh := &myHeap{}
	hp := 1
	limit := 0
	for i := 0; i < len(nums); i++ {
		hp += nums[i]
		if nums[i] < 0 {
			heap.Push(mh, -nums[i])
		}
		if hp <= 0 {
			limit++
			add := heap.Pop(mh).(int)
			hp += add
			rest += add
		}
	}
	if hp <= rest {
		return -1
	}
	return limit
}

type Pair struct {
 a, b, index int
}

type PriorityQueue []*Pair

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
 return pq[i].a < pq[j].a
}

func (pq PriorityQueue) Swap(i, j int) {
 pq[i], pq[j] = pq[j], pq[i]
 pq[i].index = i
 pq[j].index = j
}

func (pq *PriorityQueue) Push(x interface{}) {
 n := len(*pq)
 item := x.(*Pair)
 item.index = n
 *pq = append(*pq, item)
}

func (pq *PriorityQueue) Pop() interface{} {
 old := *pq
 n := len(old)
 item := old[n-1]
 old[n-1] = nil
 item.index = -1
 *pq = old[0 : n-1]
 return item
}

func processTasks(tasks [][]int) int {
 var vt []int

 n := len(tasks)
 ts := make(map[int]bool)
 for i := 0; i < n; i++ {
  ts[tasks[i][0]] = true
  ts[tasks[i][1] + 1] = true
 }
 m := len(ts)
 for key := range ts {
  vt = append(vt, key)
 }
 sort.Ints(vt)
 mp := make(map[int]int)
 for i := 0; i < m; i++ {
  mp[vt[i]] = i
 }

 starts := make([][]int, m)
 for i := 0; i < n; i++ {
  starts[mp[tasks[i][0]]] = append(starts[mp[tasks[i][0]]], i)
 }

 ans := 0
 extra := 0
 pq := make(PriorityQueue, 0)
 heap.Init(&pq)

 for i := 0; i < m - 1; i++ {
  for len(pq) > 0 {
   if tasks[pq[0].b][1] < vt[i] {
    heap.Pop(&pq)
   } else {
    break
   }
  }

  for _, u := range starts[i] {
   heap.Push(&pq, &Pair{a: extra + tasks[u][1] - vt[i] + 1 - tasks[u][2], b: u})
  }

  currentSeg := vt[i + 1] - vt[i]
  if len(pq) > 0 {
   minSlots := pq[0].a - extra
   slotsToDel := currentSeg
   if minSlots < currentSeg {
    delta := currentSeg - minSlots
    ans += delta
    slotsToDel -= delta
   }
   extra += slotsToDel
  }
 }

 return ans
}

//作者：lucifer1004
//链接：https://leetcode-cn.com/problems/t3fKg1/solution/you-xian-dui-lie-tan-xin-rust-by-lucifer-4spv/

var dir4 = []struct{ x, y int }{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}

func escapeMaze(g [][]string) bool {
	k, n, m := len(g), len(g[0]), len(g[0][0])
	vis := make([][][][6]bool, k)
	for i := range vis {
		vis[i] = make([][][6]bool, n)
		for j := range vis[i] {
			vis[i][j] = make([][6]bool, m)
		}
	}
	// s 的最低位：是否使用了临时消除术
	// s 的其余位：0-未使用永久消除术，1-当前正位于永久消除的位置，2-已使用永久消除术
	var f func(t, x, y, s int) bool
	f = func(t, x, y, s int) bool {
		if x < 0 || x >= n || y < 0 || y >= m || t+n-1-x+m-1-y >= k || vis[t][x][y][s] {
			return false
		}
		if x == n-1 && y == m-1 {
			return true
		}
		vis[t][x][y][s] = true
		if s>>1 == 1 {
			for _, d := range dir4 {
				if f(t+1, x+d.x, y+d.y, s^6) { // 跳出永久消除的位置
					return true
				}
			}
			return f(t+1, x, y, s)
		}
		if s>>1 == 0 && g[t][x][y] == '#' && f(t, x, y, s|2) { // 尝试使用永久消除术
			return true
		}
		// 使用永久消除术已无法走到终点，遇到障碍只能使用临时消除术
		if g[t][x][y] == '#' {
			if s&1 == 1 {
				return false
			}
			s |= 1
		}
		for _, d := range dir4 {
			if f(t+1, x+d.x, y+d.y, s) {
				return true
			}
		}
		return f(t+1, x, y, s)
	}
	return f(0, 0, 0, 0)
}

//作者：endlesscheng
//链接：https://leetcode-cn.com/problems/Db3wC1/solution/dfs-48ms-by-endlesscheng-ckzn/

func minimumSwitchingTimes(source [][]int, target [][]int) int {
    have := make(map[int]int)
	for i := 0; i < len(source); i++ {
        for j := 0; j < len(source[i]); j++ {
            have[source[i][j]]++
        }
    }
    need:=make(map[int]int)
    for i := 0; i < len(target); i++ {
        for j := 0; j < len(target[i]); j++ {
            need[target[i][j]]++
        }
    }
    ans:=0
    for i, c := range need {
        if have[i] >= c{
            continue
        }
        ans+= c-have[i]
    }
    return ans
}

func maxmiumScore(cards []int, cnt int) int {
	var odd, even []int
	for i := 0; i < len(cards); i++ {
		if cards[i]&1 == 1 {
			odd = append(odd, cards[i])
		} else {
			even = append(even, cards[i])
		}
	}
	sort.Ints(even)
	sort.Ints(odd)
	ans := 0
	if cnt&1 == 1 {
		if len(even) == 0 {
			return 0
		}
		ans += even[len(even)-1]
		even = even[:len(even)-1]
		cnt--
	}

	var i, j = len(even)-1, len(odd)-1
	for cnt > 0 {
		if i < 1 && j >= 1 {
			ans += odd[j] + odd[j-1]
			j -= 2
		} else if i >= 1 && j < 1 {
			ans += even[i] + even[i-1]
			i -= 2
		}else{
			if i<1 && j<1{
				return 0
			}
			if odd[j] + odd[j-1]> even[i] + even[i-1]{
				ans += odd[j] + odd[j-1]
				j -= 2
			}else{
				ans += even[i] + even[i-1]
				i -= 2
			}
		}
		cnt -= 2
	}
	return ans
}

type myHeap struct {
	arr []int
}

func (m *myHeap) Len() int {
	return len(m.arr)
}

func (m *myHeap) Less(i, j int) bool {
	return m.arr[i] > m.arr[j]
}

func (m *myHeap) Swap(i, j int) {
	m.arr[i], m.arr[j] = m.arr[j], m.arr[i]
}

func (m *myHeap) Push(x interface{}) {
	m.arr = append(m.arr, x.(int))
}

func (m *myHeap) Pop() interface{} {
	top := m.arr[len(m.arr)-1]
	m.arr = m.arr[:len(m.arr)-1]
	return top
}
func magicTower(nums []int) int {
	rest := 0
	mh := &myHeap{}
	hp := 1
	limit := 0
	for i := 0; i < len(nums); i++ {
		hp += nums[i]
		if nums[i] < 0 {
			heap.Push(mh, -nums[i])
		}
		if hp <= 0 {
			limit++
			add := heap.Pop(mh).(int)
			hp += add
			rest += add
		}
	}
	if hp <= rest {
		return -1
	}
	return limit
}

func circleGame(toys [][]int, circles [][]int, r int) int {
	sort.Slice(circles, func(i, j int) bool {
		return circles[i][0] < circles[j][0]
	})
	ans := 0
	for i := 0; i < len(toys); i++ {
		if toys[i][2]>r{
			continue
		}
		l, h := 0, len(circles)
		for l < h {
			m := (l + h) / 2
			if toys[i][0]-toys[i][2] <= circles[m][0]+r {
                h = m
			} else {
                l = m + 1
			}
		}
		for j:= l; j < len(circles); j++ {
			if toys[i][0]-toys[i][2] < circles[j][0]-r {
				break
			}
			if in(toys[i], circles[j], r) {
				ans++
                break
			}
		}
	}
	return ans
}

func in(x, y []int, r int) bool {
	return (x[0]-y[0])*(x[0]-y[0])+(x[1]-y[1])*(x[1]-y[1]) <= (r-x[2])*(r-x[2])
}