{"raw_statement":[{"iden":"statement","content":"There are a lot of things which could be cut — trees, paper, \"the rope\". In this problem you are going to cut a sequence of integers.\n\nThere is a sequence of integers, which contains the equal number of even and odd numbers. Given a limited budget, you need to make maximum possible number of cuts such that each resulting segment will have the same number of odd and even integers.\n\nCuts separate a sequence to continuous (contiguous) segments. You may think about each cut as a break between two adjacent elements in a sequence. So after cutting each element belongs to exactly one segment. Say, $[4, 1, 2, 3, 4, 5, 4, 4, 5, 5]$ $\\to$ two cuts $\\to$ $[4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5]$. On each segment the number of even elements should be equal to the number of odd elements.\n\nThe cost of the cut between $x$ and $y$ numbers is $|x - y|$ bitcoins. Find the maximum possible number of cuts that can be made while spending no more than $B$ bitcoins."},{"iden":"input","content":"First line of the input contains an integer $n$ ($2 \\le n \\le 100$) and an integer $B$ ($1 \\le B \\le 100$) — the number of elements in the sequence and the number of bitcoins you have.\n\nSecond line contains $n$ integers: $a_1$, $a_2$, ..., $a_n$ ($1 \\le a_i \\le 100$) — elements of the sequence, which contains the equal number of even and odd numbers"},{"iden":"output","content":"Print the maximum possible number of cuts which can be made while spending no more than $B$ bitcoins."},{"iden":"examples","content":"Input\n\n6 4\n1 2 5 10 15 20\n\nOutput\n\n1\n\nInput\n\n4 10\n1 3 2 4\n\nOutput\n\n0\n\nInput\n\n6 100\n1 2 3 4 5 6\n\nOutput\n\n2"},{"iden":"note","content":"In the first sample the optimal answer is to split sequence between $2$ and $5$. Price of this cut is equal to $3$ bitcoins.\n\nIn the second sample it is not possible to make even one cut even with unlimited number of bitcoins.\n\nIn the third sample the sequence should be cut between $2$ and $3$, and between $4$ and $5$. The total price of the cuts is $1 + 1 = 2$ bitcoins."}],"translated_statement":[{"iden":"statement","content":"有许多东西可以被切割——树木、纸张、\"绳子\"。在本题中，你要切割一个整数序列。\n\n有一个整数序列，其中偶数和奇数的个数相等。在预算有限的情况下，你需要进行尽可能多的切割，使得每个 resulting segment（结果段）中奇数和偶数的个数相同。\n\n切割将序列分割为连续（相邻）的段。你可以将每次切割视为序列中两个相邻元素之间的断开。切割后，每个元素恰好属于一个段。例如，$[ 4, 1, 2, 3, 4, 5, 4, 4, 5, 5 ]$ $arrow.r$ 两次切割 $arrow.r$ $[ 4, 1 | 2, 3, 4, 5 | 4, 4, 5, 5 ]$。在每个段中，偶数的个数必须等于奇数的个数。\n\n在数字 $x$ 和 $y$ 之间进行切割的代价是 $| x -y |$ 比特币。求在总花费不超过 $B$ 比特币的前提下，最多能进行多少次切割。\n\n输入的第一行包含两个整数 $n$ ($2 lt.eq n lt.eq 100$) 和 $B$ ($1 lt.eq B lt.eq 100$) —— 序列中元素的个数和你拥有的比特币数量。\n\n第二行包含 $n$ 个整数：$a_1$, $a_2$, ..., $a_n$ ($1 lt.eq a_i lt.eq 100$) —— 序列的元素，其中偶数和奇数的个数相等。\n\n请输出在花费不超过 $B$ 比特币的前提下，最多能进行的切割次数。\n\n在第一个样例中，最优解是在 $2$ 和 $5$ 之间切割。这次切割的代价为 $3$ 比特币。\n\n在第二个样例中，即使拥有无限多的比特币，也无法进行任何一次切割。\n\n在第三个样例中，应在 $2$ 和 $3$ 之间以及 $4$ 和 $5$ 之间进行切割。切割的总代价为 $1 + 1 = 2$ 比特币。\n"},{"iden":"input","content":"输入的第一行包含两个整数 $n$ ($2 lt.eq n lt.eq 100$) 和 $B$ ($1 lt.eq B lt.eq 100$) —— 序列中元素的个数和你拥有的比特币数量。第二行包含 $n$ 个整数：$a_1$, $a_2$, ..., $a_n$ ($1 lt.eq a_i lt.eq 100$) —— 序列的元素，其中偶数和奇数的个数相等"},{"iden":"output","content":"请输出在花费不超过 $B$ 比特币的前提下，最多能进行的切割次数。"},{"iden":"examples","content":"输入\n6 4\n1 2 5 10 15 20\n输出\n1\n\n输入\n4 10\n1 3 2 4\n输出\n0\n\n输入\n6 100\n1 2 3 4 5 6\n输出\n2"},{"iden":"note","content":"在第一个样例中，最优解是在 $2$ 和 $5$ 之间切割。这次切割的代价为 $3$ 比特币。在第二个样例中，即使拥有无限多的比特币，也无法进行任何一次切割。在第三个样例中，应在 $2$ 和 $3$ 之间以及 $4$ 和 $5$ 之间进行切割。切割的总代价为 $1 + 1 = 2$ 比特币。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the sequence, and $ B \\in \\mathbb{Z} $ be the budget.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, with exactly $ \\frac{n}{2} $ even and $ \\frac{n}{2} $ odd integers.  \n\nFor each position $ i \\in \\{1, 2, \\dots, n-1\\} $, define a **cut candidate** at index $ i $ (between $ a_i $ and $ a_{i+1} $) with cost $ c_i = |a_i - a_{i+1}| $.  \n\nDefine the **prefix balance** at position $ i $ as:  \n$$\nb_i = (\\text{number of odd elements in } a_1, \\dots, a_i) - (\\text{number of even elements in } a_1, \\dots, a_i)\n$$\n\nA cut at position $ i $ is **valid** if $ b_i = 0 $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 100 $  \n2. $ 1 \\leq B \\leq 100 $  \n3. $ 1 \\leq a_i \\leq 100 $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. The sequence contains equal numbers of even and odd integers: $ \\sum_{i=1}^n \\mathbf{1}_{\\{a_i \\text{ odd}\\}} = \\sum_{i=1}^n \\mathbf{1}_{\\{a_i \\text{ even}\\}} = \\frac{n}{2} $  \n\n**Objective**  \nFind the maximum number of valid cuts $ k $ such that:  \n- Each cut is at a position $ i \\in \\{1, \\dots, n-1\\} $ with $ b_i = 0 $,  \n- The sum of costs of selected cuts $ \\leq B $,  \n- Cuts are chosen to maximize $ k $.  \n\nThat is, let $ C = \\{ c_i \\mid i \\in \\{1, \\dots, n-1\\}, b_i = 0 \\} $.  \nFind the maximum $ k $ such that there exists a subset of $ k $ elements from $ C $ whose sum is $ \\leq B $.","simple_statement":null,"has_page_source":false}