题面描述

有一个总空间为 $100$ 字节的堆，现要从中新申请一块内存，内存分配原则为：

1. 优先紧接着前一块已使用内存。
2. 分配空间足够且最接近申请大小的空闲内存。

思路

这道题的思路是首先对已分配的内存块进行合法性检查，确保所有内存块的起始地址和大小在堆的范围内且没有重叠。然后，将已分配的内存块按照起始地址排序，接着识别出所有空闲的内存区域。接下来，根据内存分配的优先原则，优先选择紧接着前一块已使用内存的空闲区，并在满足申请大小的空闲区中选择最接近申请大小的区域。最后，若找到合适的空闲区，则输出其起始地址，否则输出 -1 表示分配失败。通过这种方法，能够深入有效地管理和分配堆内存，确保分配的最优性和合理性。

题目内容

有一个总空间为 $100$ 字节的堆，现要从中新申请一块内存，内存分配原则为：优先紧接着前一块已使用内存，分配空间足够且最接近申请大小的空闲内存。

输入描述

第 $1$ 行是 $1$ 个整数，表示期望申请的内存字节数

第 $2$ 到第 $N$ 行是用空格分割的两个整数，表示当前已分配的内存的情况，每一行表示一块已分配的连续内存空间，每行的第 $1$ 和第 $2$ 个整数分别表示偏移地址和内存块大小，如：

0 1

3 2

表示 $0$ 偏移地址开始的 $1$ 个字节和 $3$ 偏移地址开始的 $2$ 个字节已被分配，其余内存空闲。

输出描述

若申请成功，输出申请到内存的偏移；

若申请失败，输出 $-1$ 。

备注

若输入信息不合法或无效，则申请失败

若没有足够的空间供分配，则申请失败

堆内存信息有区域重叠或有非法值等都是无效输入

样例1

输入

1
0 1
3 2

输出

1

说明

堆中已使用的两块内存是偏移从 $0$ 开始的 $1$ 字节和偏移从 $3$ 开始的 $2$ 字节，空闲的两块内存是偏移从 $1$ 开始 $2$ 个字节和偏移从 $5$ 开始 $95$ 字节，根据分配原则，新申请的内存应从 $1$ 开始分配 $1$ 个字节，所以输出偏移为 $1$ 。