def knapsack(weights, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        for j in range(capacity, weights[i] - 1, -1):
            dp[j] = max(dp[j], dp[j - weights[i]] + weights[i])  # 修正状态转移方程

    return capacity - dp[capacity]  # 返回最小剩余空间


if __name__ == '__main__':
    V = int(input())
    n = int(input())
    vlist = []
    for i in range(n):
        vlist.append(int(input()))
    print(knapsack(vlist, V))

for i in range(n):  # 遍历所有物品
    for j in range(capacity, weights[i] - 1, -1):  # 从大到小遍历背包容量
        dp[j] = max(dp[j], dp[j - weights[i]] + weights[i])  # 状态转移方程

for i in range(n):

for j in range(capacity, weights[i] - 1, -1):

dp[j] = max(dp[j], dp[j - weights[i]] + weights[i])

def knapsack(value, weight, capacity):
    n = len(value)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]  # 实际长度为容量加1（要考量容量为0的情况）
    # 0行和0列一定为0
    for i in range(1, n + 1):  # 要添加的物品价值为i时(按行遍历)
        for j in range(1, capacity + 1):  # 遍历每一种容量的背包 j为容量
            if weight[i - 1] <= j:
                # 当容量足够加入该物品时,进行对比
                """如果没有这个物品介入时,同为j容量的背包能装得的物品最大价值dp[i - 1][j]
                以及如果选择装入这个物品(value[i - 1])与剩下容量能装入的最大价值dp[i - 1][j - weight[i - 1]]的和
                在两者之间比较最大值取就行
                """
                dp[i][j] = max(value[i - 1] + dp[i - 1][j - weight[i - 1]], dp[i - 1][j])
            else:  # 当要添加的物品加不进背包时候,最优解就是同容量背包不加这个物品的时候的最优解
                dp[i][j] = dp[i - 1][j]

    # 最后一行的capacity列的值就是所求的最优解, 即容量为capacity的背包能装入的物品最大价值
    return dp[n][capacity]


if __name__ == '__main__':
    T, M = map(int, input().split(' '))
    # T就是背包容量
    tlist = []  # 存每个物品的耗时(即物品需要的背包容量)
    mlist = []  # 存每个物品价值
    for i in range(M):
        t, m = map(int, input().split(' '))
        tlist.append(t)
        mlist.append(m)

    print(knapsack(mlist, tlist, T))

def Binexp(a,n):
    r = 1
    while n > 0:
        if n % 2 == 1	:  #如果n的二进制最后一位是1，则乘入r
            r *= a
        a *= a  #a更新到下一个为偶次方的值上
        n //= 2  #n //= 2的含义就是将n的二进制的最后一位消灭掉
    return r

def Binexp(a, n):
    r = 1
    while n > 0:
        if n & 1:  #n & 1表示n与1的二进制做位运算，只看最后一位是否相等，相等说明n的二进制最后一位是1
            r *= a
        a *= a
        n >>= 1  # n 对2整除并向下取整等效于将n的二进制右移一位
    return r

def qumo(a, n, m):
    a = a % m  # 将基数 a 对模数 m 取模，减少后续计算中的数值大小
    r = 1      # 初始化结果 r 为 1（因为任何数的 0 次幂都是 1）
    while n > 0:  # 当指数 n 大于 0 时继续循环
        if n & 1 == 1:  # 如果 n 的二进制最低位是 1
            r = (r * a) % m  # 将当前的 a 乘入结果 r，并对 m 取模
        a = (a * a) % m  # 将 a 平方，并对 m 取模
        n >>= 1  # 将 n 右移一位（相当于 n = n // 2）
    return r  # 返回最终结果

print((qumo(9, 10000,10**9+7)-2*qumo(8,10000,10**9+7)+qumo(7,10000,10**9+7))%(10**9+7))

import numpy as np
def fibonacci3(n):
    A = np.array([[0, 1], [1, 1]], dtype=np.object_)
    R = np.eye(A.shape[0], dtype=np.object_)
    while n > 0:
        if n & 1:
            R = np.dot(R, A)
        A = np.dot(A, A)
        n >>= 1
    return R[1,0]

import numpy as np

a = np.array([1, 2, 3])
b = np.array([4, 5, 6])

result = np.dot(a, b)
print(result)  # 输出：32 (1*4 + 2*5 + 3*6)

A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])

result = np.dot(A, B)
print(result)
# 输出：
# [[19 22]
#  [43 50]]

A = np.random.rand(2, 3, 4)
B = np.random.rand(2, 4, 5)

result = np.dot(A, B)
print(result.shape)  # 输出：(2, 3, 5)

A = np.array([[1, 2], [3, 4]])
B = np.array([[5, 6], [7, 8]])

result = A @ B  # 等价于 np.dot(A, B)
print(result)
# 输出：
# [[19 22]
#  [43 50]]

def min_moves_to_balance_groups(n, groups, L, R):
    # 计算总学生数
    total_students = sum(groups)
    
    # 检查是否可行
    if n * L > total_students or total_students > n * R:
        return -1  # 不可能满足条件

    # 初始化正偏差和负偏差
    excess = 0  # 需要移出的学生总数
    deficit = 0  # 需要移入的学生总数

    # 计算每个组的调整需求
    for group in groups:
        if group < L:
            deficit += L - group  # 负偏差
        elif group > R:
            excess += group - R  # 正偏差

    # 最小移动次数为正偏差和负偏差的最大值
    moves = max(deficit, excess)
    return moves

# 读取输入
n = int(input().strip())
groups = list(map(int, input().strip().split()))
L, R = map(int, input().strip().split())

# 调用函数并输出结果
result = min_moves_to_balance_groups(n, groups, L, R)
print(result)

def min_moves_to_equalize_cards(N, A):
    # 计算平均值
    total_cards = sum(A)
    average = total_cards // N

    # 初始化移动次数和平衡变量
    moves = 0
    balance = 0

    # 遍历每堆纸牌
    for i in range(N):
        # 计算当前堆与平均值的差值
        diff = A[i] - average

        # 更新平衡变量
        balance += diff

        # 如果平衡变量不为零，说明需要移动纸牌
        if balance != 0:
            moves += 1

    return moves

# 读取输入
N = int(input())
A = list(map(int, input().split()))

# 计算并输出最小移动次数
print(min_moves_to_equalize_cards(N, A))

# 简单的递归搜索加上记忆化搜索，时间复杂度仍然很高
def jump(n):
    # 如果n在记忆中，就直接返回
    if n in mem:
        return mem[n]
    if n == 1:
        sum = 1
    elif n == 2:
        sum = 2
    else:
        sum = jump(n - 1) + jump(n - 2)
    mem[n] = sum
    return sum


"""利用递归过程中的“推”的过程，便是基本的递推优化"""

"""注意，这里是优化时间"""
def optimized_jump(n):
    f = [0] * (n + 1)
    f[1] = 1
    f[2] = 2
    for i in range(3, n + 1):
        f[i] = f[i - 1] + f[i - 2]  # 这个递推公式也就是dfs的状态转移公式
    return f[n]


# 上面的代码也可以换成这种形式的写法，核心都是从小到大递推
"""注意，这里是对上面的函数优化空间"""
def optimized_jump2(n):
    if n == 1: return 1
    if n == 2: return 2
    newf = 0
    temp1 = 1
    temp2 = 2
    for i in range(3, n + 1):
        newf = temp1 + temp2
        temp1 = temp2
        temp2 = newf

    return newf


if __name__ == '__main__':
    mem = [0] * 100

    # 明显快了很多
    # print("Starting:" ,jump(400))
    # print("Starting:", optimized_jump(400))
    print("Starting:", optimized_jump2(300))

# 考虑01背包问题的解决方式
def max_money(T):
    if T == 1:
        return moneyList[0]
    if T == 2:
        return max(moneyList[0], moneyList[1])
    # moneylist[T-1]是最后一个店铺的金钱数，这里考虑的问题就是，如果多一个店铺，是在原有基础上保留，还是退回一个店铺选择窃取这个新出现的店铺
    return max(max_money(T - 2) + moneyList[T - 1], max_money(T - 1))

# 考虑递推优化的方式
"""当遇到第x家店铺时，考虑的是选择下一家（x+1）店铺dfs(x + 1)或者就选择这一家，那么下次考虑的就是第x+2家店铺dfs(x + 2) + moneyList[x]"""
def dfs(x):
    if x > T: return 0
    return max(dfs(x + 1), dfs(x + 2) + moneyList[x-1])

mem = [0] * (T + 2)  #如此定义长度是为了防止x > T的情况出现，大于T的时候自然存0就行
def memSearch(x):
    if mem[x] != 0:
        return mem[x]
    if x > T:
        sums = 0
    else:
        sums = max(dfs(x + 1), dfs(x + 2) + moneyList[x - 1])
    mem[x] = sums
    return sums

f = [0] * (T + 3)  # f[i] 表示从第i个店铺开始洗劫能获取的最大现金数
def recursFind(T):
    # 从T到1倒叙进行
    for i in range(T, 0, -1):
        f[i] = max(f[i + 1], f[i + 2] + moneyList[i - 1])
    return f[1]

def recursFindPlus(T):
    newf = 0
    temp1 =0
    temp2 = 0
    for i in range(T):
        newf = max(temp1, temp2 + moneyList[i])
        temp2 = temp1
        temp1 = newf  #temp1始终存的是上一次的最优的结果，temp2存的是上上次的最优结果
        print("newf:",newf)
    return newf

# 考虑01背包问题的解决方式
def max_money(T):
    if T == 1:
        return moneyList[0]
    if T == 2:
        return max(moneyList[0], moneyList[1])
    # moneylist[T-1]是最后一个店铺的金钱数，这里考虑的问题就是，
    # 如果多一个店铺，是在原有基础上保留，还是退回一个店铺选择窃取这个新出现的店铺
    return max(max_money(T - 2) + moneyList[T - 1], max_money(T - 1))


# 考虑递归的方式
"""当遇到第x家店铺时，考虑的是选择下一家（x+1）店铺dfs(x + 1)或者就选择这一家，
那么下次考虑的就是第x+2家店铺dfs(x + 2) + moneyList[x]"""


def dfs(x):
    if x > T:
        return 0
    return max(dfs(x + 1), dfs(x + 2) + moneyList[x - 1])


# 记忆化搜索优化递归
def memSearch(x):
    if mem[x] != 0:
        return mem[x]
    if x > T:
        sums = 0
    else:
        sums = max(dfs(x + 1), dfs(x + 2) + moneyList[x - 1])
    mem[x] = sums
    return sums


# 倒叙的递推
def recursFind(T):
    # 从T到1倒叙进行
    for i in range(T, 0, -1):
        f[i] = max(f[i + 1], f[i + 2] + moneyList[i - 1])
    return f[1]


# 递推并且进行空间优化
def recursFindPlus(T):
    temp1 = 0
    temp2 = 0
    newf = 0
    for i in range(T):
        newf = max(temp1, temp2 + moneyList[i])
        temp2 = temp1
        temp1 = newf  # temp1始终存的是上一次的最优的结果，temp2存的是上上次的最优结果
        print("newf:", newf)
    return newf


if __name__ == '__main__':
    T = int(input())
    moneyList = list(map(int, input().split(" ")))
    
    print(max_money(T))
    
    print(dfs(1))
    
    mem = [0] * (T + 2)
    print(memSearch(1))
    
    f = [0] * (T + 3)  # f[i] 表示从第i个店铺开始洗劫能获取的最大现金数
    print(recursFind(T))
 
    print(recursFindPlus(T))

# dfs存坐标，控制访问的边界
def dfs(x, y):
    if x > r or y > r:
        return 0
    # 求最优的子问题，
    # 就是看往左dfs(x + 1, y)或者往右dfs(x, y + 1)的最大值，
    # 记得加上当前值tangleList[x][y]（因为算的是和）
    return max(dfs(x + 1, y), dfs(x + 1, y + 1)) + tangleList[x - 1][y - 1]


# 记忆化搜索优化
def dfs_mem(x, y):
    if mem[x][y] != 0:
        return mem[x][y]
    sums = 0
    if x > r or y > r:
        sums = 0
    # 求最优的子问题，
    else:
        sums = max(dfs_mem(x + 1, y), dfs_mem(x + 1, y + 1)) + tangleList[x - 1][y - 1]
    mem[x][y] = sums  # 记录值
    # print(mem)
    return sums


# 递推优化
# 从下往上推，第一个点一定是终点
def dp():
    for i in range(r, 0, -1):
        for j in range(1,i+1):
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + tangleList[i - 1][j - 1]
            # print(" :", f)
    return f[1][1]


# 从上往下推最后一个点不一定，但是起点一定是第一个点1，1
# f[i][j]就表示以第i行第j列为终点产生的最大的路径和，而题目只要求到达底部的最大路径所以说要找底部f[r]中的最大值
def dp_reverse():
    for i in range(1,r+1):
        for j in range(1,i+1):
            f[i][j] = max(f[i - 1][j], f[i - 1][j - 1]) + tangleList[i - 1][j - 1]
            # print(" :", f)
    return max(f[r])

# 递推空间优化
# 因为第i行第j列的状态只是由上一个的状态转移过来的，i是有规律一直往下的
# 则 f_s[j] = max(f_s[j], f_s[j + 1]) + tangleList[i - 1][j - 1]就表示上一行的第j列的最优与第j+1列的最优的最大值加上当前i行j列的值
def dp_space():
    for i in range(r, 0, -1):
        for j in range(1,i+1):
            f_s[j] = max(f_s[j], f_s[j + 1]) + tangleList[i - 1][j - 1]
    return f_s[1]



if __name__ == '__main__':
    r = int(input())
    tangleList = [[0] * r for i in range(r)]

    # 输入三角
    for i in range(r):
        tangleList[i] = list(map(int, input().split())) + [0] * (r - i + 1)
    # print(tangleList)

    mem = [[0] * (i + 2) for i in range(r+2)]
    print(dfs_mem(1, 1))

    # f = [[0] * (r + 2) for i in range(r + 2)]
    # print(dp())

    f = [[0] * (r + 2) for i in range(r + 2)]
    print(dp_reverse())

    f_s = [0] * (r + 2)
    print(dp_space())

    # print(dp_space2())

from datetime import datetime

def calculate_time_difference():
    # 定义时间格式
    time_format = "%Y-%m-%d-%H:%M"
    
    # 提示用户输入两个时间
    time_str1 = input("请输入第一个时间（格式：YYYY-MM-DD-HH:MM）：")
    time_str2 = input("请输入第二个时间（格式：YYYY-MM-DD-HH:MM）：")
    
    try:
        # 将时间字符串转换为datetime对象
        time1 = datetime.strptime(time_str1, time_format)
        time2 = datetime.strptime(time_str2, time_format)
        
        # 计算两个时间之间的差值（timedelta对象）
        time_difference = time2 - time1
        
        # 将时间差转换为分钟数
        minutes_difference = time_difference.total_seconds() / 60
        
        # 输出结果
        print(f"两个时间之间的分钟数间隔为：{minutes_difference}分钟")
    except ValueError as e:
        print("输入的时间格式不正确，请确保格式为YYYY-MM-DD-HH:MM。错误信息：", e)

# 调用函数
calculate_time_difference()

# 简单暴力
def solve(x):
    # 若超过最大台阶数n-1，即处于第n个或者更大，说明已经到达顶部，则返回0
    if x == 0 or x == 1:
        return 0
    else:  # 考虑最后一步，最后一步是跨2层的能量低一点还是跨1层能量低一点
        return min(solve(x - 1) + cost[x - 1], solve(x - 2) + cost[x - 2])


# 记忆化搜索优化
def solve_mem(x):
    if (mem[x] != 0):
        return mem[x]
    if x == 0 or x == 1:
        sums = 0
    else:
        sums = min(solve(x - 1) + cost[x - 1], solve(x - 2) + cost[x - 2])
    #     利用sums存变量并返回结果
    mem[x] = sums
    return sums


# 递推优化
def cursion_solve(x):
    # 到第n层就结束，f[i]表示的就是从开始到第i层的最小消费
    for i in range(2,x+1):  # 从顶部n开始向下
        # 要包含第2层并且不考虑第0和1层的消费（因为可以直接选从0或者1开始，自然是0）
        # i 从2开始 ，f[2]就表示从开始到第三层的最小消费，自然是min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2])
        f[i] = min(f[i - 1] + cost[i - 1], f[i - 2] + cost[i - 2])
    # print(f)

    # 返回f[n]表示从开始到第n层的最小消费
    return f[n]


if __name__ == '__main__':
    # 总共0到n-1层楼梯
    n = int(input())
    #  cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用
    cost = list(map(int, input().split(' ')))
    # solve(x)表示的是从第x层开始到顶能取得的最大数

    print(solve(n))

    mem = [0] * (n + 1)
    print(solve_mem(n))

    # f[i]表示从第i层开始到达顶部的最小花费
    f = [0] * (n + 1)
    print(cursion_solve(n))

# 递归加记忆化搜索
def L(x):
    if x in memo:
        return memo[x]
    if x == len(num) - 1:
        return 1

    max_len = 1
    for i in range(x + 1, len(num)):
        if num[i] > num[x]:
            # 与以下一个点为起点的最短路径长度进行比较并做更新
            max_len = max(max_len, L(i) + 1)

    memo[x] = max_len
    return max_len


def recursion_search():
    n = len(num)  # 获取数组长度
    f = [1] * n   # 初始化数组，每个位置的最长递增子序列长度至少为1

    for x in range(n):  # 遍历每个位置
        for i in range(x):  # 检查所有小于x的位置
            if num[x] > num[i]:  # 如果当前元素大于之前的某个元素
                f[x] = max(f[x], f[i] + 1)  # 更新以x为结尾的最长递增子序列长度

    return max(f)  # 返回最长递增子序列的最大长度


if __name__ == '__main__':
    n = int(input())
    num = list(map(int, input().split(' ')))

    """定义哈希表存储以x为起点的最大路径长度"""
    memo = {}
    print(L(0))  # 最长递增子序列为1，2，3，4，5长度为5

    f = [0] * (n + 1)  # f[i]表示以num[i]结尾的最长子序列长度
    print(recursion_search())  # 最长递增子序列为1，2，3，4，5长度为5

def dfs(x, spV, spM):
    if x > N:
        return 0
    # 若装不下当前物品，就继续看下一个物品
    if spV < vlist[x] or spM < mlist[x]:
        return dfs(x + 1, spV, spM)
    # 若装得下当前物品，就看看能得到的最大价值
    # 就是看看在不装当前物品的情况下，能得到的最大价值，和装当前物品的情况下，能得到的最大价值
    return max(dfs(x + 1, spV, spM), wlist[x] + dfs(x + 1, spV - vlist[x], spM - mlist[x]))


def dfs_mem(x, spV, spM):
    # 若之前的状态有记录，就直接返回
    if mem[x][spV][spM] != 0:
        return mem[x][spV][spM]
    if x > N:
        return 0
    sums = 0
    # 若装不下当前物品，就继续看下一个物品
    if spV < vlist[x] or spM < mlist[x]:
        sums = dfs(x + 1, spV, spM)
    else:
        sums = max(dfs(x + 1, spV, spM), wlist[x] + dfs(x + 1, spV - vlist[x], spM - mlist[x]))
    mem[x][spV][spM] = sums
    return sums


def dfs_dp():
    # i代表当前是考虑第i个物品，j代表当前的剩余体积，k代表当前剩余重量
    for i in range(N, 0, -1):
        for j in range(V + 1):
            for k in range(M + 1):
                # j代表当前的剩余体积，k代表当前剩余重量，有一个被超了就无法装下物品
                # 那么等同于不装这个物品，考虑从第x+1个物品开始，剩余体积重量不减的最优解
                if j < vlist[i] or k < mlist[i]:
                    dp[i][j][k] = dp[i + 1][j][k]
                else:
                    # 能装下，就考虑，是装下这个物品，考虑本物品价值加上考虑从第x+1个物品开始剩余体积重量对应减去本物品的体积重量的最优解
                    # 还是不装这个物品，考虑从第x+1个物品开始，剩余体积重量不减的最优解
                    # 即，如果装了第x个物品，那么从第x+1个物品开始的剩余体积重量当然少
                    dp[i][j][k] = max(dp[i + 1][j][k], wlist[i] + dp[i + 1][j - vlist[i]][k - mlist[i]])
    # dp[1][V][M]表示从第1个物品开始考虑，此时剩余体积是V剩余重量M，得到的最优价值
    return dp[1][V][M]


def dfs_dp_reverse():
    for i in range(1, N + 1):
        for j in range(V + 1):
            for k in range(M + 1):
                if j < vlist[i] or k < mlist[i]:
                    dp[i][j][k] = dp[i - 1][j][k]
                else:
                    dp[i][j][k] = max(dp[i - 1][j][k], wlist[i] + dp[i - 1][j - vlist[i]][k - mlist[i]])
    return dp[N][V][M]


# 二维优化

def dfs_dp_two():
    for x in range(1, N + 1):
        for j in range(V, vlist[x]-1 , -1):
            for k in range(M, mlist[x] -1, -1):
                dp_two[j][k] = max(dp_two[j][k], wlist[x] + dp_two[j - vlist[x]][k - mlist[x]])
    return dp_two[V][M]


if __name__ == '__main__':
    N, V, M = map(int, input().split(' '))
    # 先初始化第0个物品的体积重量价值为0
    vlist = [0]  # 体积数列
    mlist = [0]  # 重量数列
    wlist = [0]  # 价值数列
    for _ in range(N):
        v, m, w = map(int, input().split(' '))
        vlist.append(v)
        mlist.append(m)
        wlist.append(w)

    # 记忆化搜索
    mem = [[[0] * 1010] * (1010) for _ in range(1010)]
    print(dfs_mem(1, V, M))

    # 动态规划
    dp = [[[0] * (M + 2) for _ in range(V + 2)] for _ in range(N + 2)]
    print(dfs_dp())

    # 二维优化
    dp_two = [[0] * (M + 2) for _ in range(V + 2)]
    print(dfs_dp_two())

def dfs_dp_two():
    for x in range(1, N + 1):
        for j in range(V, vlist[x]-1 , -1):
            for k in range(M, mlist[x] -1, -1):
                dp_two[j][k] = max(dp_two[j][k], wlist[x] + dp_two[j - vlist[x]][k - mlist[x]])
    return dp_two[V][M]

# x表示当前枚举到哪个物品，spV表示背包当前剩余的容量
def solve(x, spV):
    sums = 0
    if f[x][spV] != 0:
        return f[x][spV]
    if x > N:
        return 0
    if spV < vlist[x]:
        # 当前物品体积超过剩余，就看下一个
        sums = solve(x + 1, spV)
    else:
        # 没有超，开始公式看能否取出当前物品,不取当前物品就考虑下一个物品,取了当前物品,下次还可以考虑当前物品
        sums = max(solve(x + 1, spV), solve(x, spV - vlist[x]) + wlist[x])
    f[x][spV] = sums
    return f[x][spV]


def solve2():
    for i in range(N, 0, -1):
        for j in range(0, V + 1):
            if j < vlist[i]:
                m[i][j] = m[i + 1][j]
            else:
                m[i][j] = max(m[i + 1][j], m[i][j - vlist[i]] + wlist[i])
    # print(m)
    return m[1][V]


def solve3():
    for i in range(1, N + 1):
        for j in range(vlist[i], V + 1):
            t[j] = max(t[j], t[j - vlist[i]] + wlist[i])
    # print(m)
    return t[V]


if __name__ == '__main__':
    N, V = map(int, input().split(' '))
    vlist = [0]
    wlist = [0]
    for i in range(N):
        v, w = map(int, input().split(' '))
        vlist.append(v)
        wlist.append(w)
    # print(vlist,wlist)
    # 记忆化搜索
    f = [[0] * (V + 2) for i in range(N + 2)]
    # print(solve(1, V))

    # 递推
    m = [[0] * (V + 2) for i in range(N + 2)]
    print(solve2())

    # 空间优化
    t = [0 for i in range(V + 2)]
    print(solve3())

"""01背包"""
def solve3():
    for i in range(1, N + 1):
        for j in range(V, vlist[i] - 1,-1):
            t[j] = max(t[j], t[j - vlist[i]] + wlist[i])
    # print(m)
    return t[V]

def solve3():
    for i in range(1, N + 1):
        for j in range(vlist[i], V + 1):
            t[j] = max(t[j], t[j - vlist[i]] + wlist[i])
    # print(m)
    return t[V]


# 空间优化
t = [0 for i in range(V + 2)]
print(solve3())

def solve3():
    for i in range(1, N + 1):
        for j in range(vlist[i], V + 1):
            t[j] = max(t[j], t[j - vlist[i]] + wlist[i])
    return t[V]

class Solution(object):
    def maxProductAfterCutting(self,n):
        if n == 2:
            return 1
        if n == 3:
            return 2
        product = 1
        while n > 4:
            product *= 3
            n -= 3
        product *= n
        return product

# 检查 right 是否在数组范围内，并且是否等于目标值
if right < len(dataList) and dataList[right] == x:
    return right + 1  # 返回索引 + 1
return -1  # 如果未找到，返回 -1

def isBlue(num, x):
    """
    判断 num 是否小于 x。
    :param num: 当前比较的数值
    :param x: 目标值
    :return: 如果 num < x，返回 True，否则返回 False
    """
    return num < x

def binary_search(x, dataList):
    """
    使用二分查找算法查找目标值 x 在 dataList 中的位置。
    :param x: 目标值
    :param dataList: 已排序的数组
    :return: 如果找到目标值，返回其索引 + 1；否则返回 -1
    """
    left = -1
    right = len(dataList)  # 确保 right 的值正确
    while left + 1 < right:
        middle = (right + left) >> 1  # 使用位运算计算中间值，就是向下整除2的意思
        if isBlue(dataList[middle], x):
            left = middle
        else:
            right = middle
    # 检查 right 是否在数组范围内，并且是否等于目标值
    if right < len(dataList) and dataList[right] == x:
        return right + 1  # 返回索引 + 1
    return -1  # 如果未找到，返回 -1

if __name__ == '__main__':
    # 读取输入
    n, m = map(int, input().split())
    dataList = list(map(int, input().split()))
    targetList = list(map(int, input().split()))

    # 对每个目标值进行二分查找
    for target in targetList:
        index = binary_search(target, dataList)
        print(index, end=' ')

def check(num):
    return num*num*num < x

def check(num, n):
    """
    检查 num 的三次方是否小于 n。
    :param num: 当前的中间值
    :param n: 目标值
    :return: 如果 num^3 < n，返回 True，否则返回 False
    """
    return num * num * num < n

def binary_search(n):
    """
    使用二分查找算法计算 n 的三次方根。
    :param n: 目标值
    :return: n 的三次方根，保留8位小数
    """
    left, right = -100, 100  # 三次方根的范围
    while right - left > 1e-8:  # 精度控制
        mid = (left + right) / 2  # 计算中间值
        if check(mid, n):
            left = mid  # 如果 mid 的三次方小于 n，更新左边界
        else:
            right = mid  # 否则，更新右边界
    result = round(right, 8)  # 返回保留8位小数的结果
    # 在返回结果时，先将 right 保留8位小数，得到 result。
    # 使用字符串格式化：
    # 在返回结果时，使用 f"{right:.8f}"，这会将 right 格式化为一个字符串，并确保保留8位小数。
    # 即使结果是整数或小于8位的小数，也会自动补零
    return  f"{right:.8f}"

if __name__ == '__main__':
    n = eval(input())  # 输入目标值
    result = binary_search(n)  # 计算三次方根
    print(result)  # 输出结果

def check(num, n):
    """
    检查 num 的三次方是否小于 n。
    :param num: 当前的中间值
    :param n: 目标值
    :return: 如果 num^3 < n，返回 True，否则返回 False
    """
    return num * num * num <= n

def binary_search(n):
    """
    使用二分查找算法计算 n 的三次方根。
    :param n: 目标值
    :return: n 的三次方根，保留8位小数
    """
    left, right = 0, 100001# 三次方根的范围要囊括所有情况(从1到100000)
    while right - left > 1:  # 精度控制
        mid = (left + right)>>1 # 计算中间值
        if check(mid, n):
            left = mid  # 如果 mid 的三次方小于 n，更新左边界
        else:
            right = mid  # 否则，更新右边界
    # 使用字符串格式化确保结果保留0位小数
    return f"{left:.0f}"

if __name__ == '__main__':
    n = int(input())  # 输入目标值
    result = binary_search(n)  # 计算三次方根
    print(result)  # 输出结果

def monthly_payment(P, r, n):
    """
    计算每月还款数。
    :param P: 贷款金额
    :param r: 月利率
    :param n: 还款总期数
    :return: 每月还款数
    """
    return P * r * (1 + r) ** n / ((1 + r) ** n - 1)

def monthly_payment(P, r, n):
    """
    计算每月还款数。
    :param P: 贷款金额
    :param r: 月利率
    :param n: 还款总期数
    :return: 每月还款数
    """
    if r == 0:
        return P / n
    else:
        try:
            exp_term = (1 + r) ** n
            return P * r * exp_term / (exp_term - 1) < M
        except OverflowError:
            return False  # 如果发生溢出，说明过大，r值还需要减小

import math


def monthly_payment(P, r, n):
    """
    计算每月还款数。
    :param P: 贷款金额
    :param r: 月利率
    :param n: 还款总期数
    :return: 每月还款数
    """
    if r == 0:
        return P / n
    else:
        try:
            exp_term = (1 + r) ** n
            return P * r * exp_term / (exp_term - 1) < M
        except OverflowError:
            return False  # 如果发生溢出，说明过大，r值还需要减小


def find_monthly_interest_rate(P, M, n, tol=0.00001):
    """
    使用二分法求解月利率。
    :param P: 贷款金额
    :param M: 每月还款数
    :param n: 还款总期数
    :param tol: 容忍度
    :return: 月利率（百分数）
    """
    r_low = 0
    r_high = 3  # 数据保证答案不超过 300.0%
    # r_mid = (r_low + r_high) / 2

    while r_high - r_low > tol:
        r_mid = (r_low + r_high) / 2
        if monthly_payment(P, r_mid, n):
            r_low = r_mid
        else:
            r_high = r_mid

    return round(r_high * 100, 1)


# 读取输入
P, M, n = map(int, input().split())

# 计算月利率
r = find_monthly_interest_rate(P, M, n)
print(r)

def recursion_search():
    for x in range(n):  # 外层遍历每个位置的元素
        for i in range(x):  # 检查所有索引小于x的位置
            if num[x] > num[i]:  # 如果当前元素x大于x之前的某个元素
                # 就是取目前来说运算得到的以x元素结尾的最大子序列长度，
                # 还是取以目前指向的以i结尾的最大序列长度加1的问题
                f[x] = max(f[x], f[i] + 1)  # 更新以x为结尾的最长递增子序列长度

    return max(f)  # 返回最长递增子序列的最大长度


def recursive_sum():
    for x in range(n):  # 外层遍历每个位置的元素
        for i in range(x):  # 检查所有索引小于x的位置
            if num[x] > num[i]:  # 如果当前元素x大于x之前的某个元素
                # 就是取目前来说运算得到的以x元素结尾的最大子序列和，
                # 还是取以目前指向的以i结尾的最大序列和加上x元素的问题
                s[x] = max(s[x], s[i] + num[x])  # 更新以x为结尾的最长递增子序列和

    return max(s)  # 返回最长递增子序列和的最大值


if __name__ == '__main__':
    n = int(input("输入列表元素个数："))
    print("输入列表：", end="")
    num = list(map(int, input().split(' ')))
    f = [1] * n  # 初始化数组，每个位置的最长递增子序列长度至少为1
    print(f"最长子序列的长度:{recursion_search()}")  # 最长递增子序列为1，2，3，4，5， 长度为5
    s = [num[0]] * n  # 初始化数组，每个位置的最长递增子序列和至少为num[0]
    print(f"最大的子序列前缀和：{recursive_sum()}")  # 最长递增子序列和为1+2+3+4+5 = 15

# 判断是否在索引为i（实际是i+1块）地毯内
def isIn(i):
    if xrange[i][0] <= x <= xrange[i][1] and yrange[i][0] <= y <= yrange[i][1]:
        return True
    else:
        return False


def findPath():
    flag = -1
    for i in range(n):
        if isIn(i):
            # 如果在地毯内就更新flag
            flag = i
            # print("Found the path at index", i)
    return flag


if __name__ == '__main__':
    n = int(input())
    """
    xrange[i]：表示索引为i，即第i+1块地毯所占的x轴上的范围
    yrange[i]：表示索引为i，即第i+1块地地毯所占的y轴上的范围
    """
    xrange = []
    yrange = []
    for i in range(n):
        a, b, g, k = map(int, input().split())
        xrange.append([a, a + g])
        yrange.append([b, b + k])
    x, y = map(int, input().split())
    # print("xrange:", xrange)
    # print("yrange:", yrange)
    m = findPath()
    if m == -1:
        print(m)
    else:
        # 记得索引是0开始，索引为0的地毯是第1块地毯
        print(m + 1)