{"raw_statement":[{"iden":"statement","content":"Diego is out with $3$ of his friends (Jorge, Juan and Bob), when out of nowhere one of them realizes that there is a gigantic bar or chocolate, every single one of them is greedy so they want to eat as much chocolate as possible.\n\nAfter many hours of arguing who gets to eat the most chocolate they came up with the following: the best division is one such that the difference between the person who eats the most chocolate and the person who eats the least chocolate is as small as possible.\n\nAs they are about to begin distributing the chocolate bar they came up to a realization, this bar has the shape of a rectangle, has exactly length $L$ and also has exactly $N -1$ different cutting spots, each spot located at a specific position $x_i$ (assuming that the chocolate bar begins in position $0$). So they must cut the chocolate bar in exactly $3$ of the cutting spots.\n\nHelp Diego find out the optimal way of dividing the chocolate bar in $4$ such that the difference between whoever eats less and whoever eats most is minimal.\n\nA line with 2 integers, $N, L$ $(4 <= N <= 10^5, 4 <= L <= 10^(15))$, the amount of cutting spots within the chocolate bar and the length of the chocolate bar.\n\nFollowed by a line with $N -1$ integers in increasing order, representing the position of the ith cutting spot $(1 <= x_i < 10^(15))$. It's guaranteed that $x_i < x_{i + 1}$ for $1 <= i < N -1$.\n\nA single integer $M$, the minimal delta between the smallest and biggest piece of chocolate if we divide the bar into exactly $4$ pieces.\n\nIn the test case, given the positions it's the equivalent of saying that we have 8 pieces of the following lengths: 3 1 1 3 2 2 3 3 There are 2 optimal answers, we can either split it in such a way that the 4 chocolate pieces the friends are going to eat are of sizes 5 5 5 3, or of sizes 4 4 4 6.\n\n"},{"iden":"input","content":"A line with 2 integers, $N, L$ $(4 <= N <= 10^5, 4 <= L <= 10^(15))$, the amount of cutting spots within the chocolate bar and the length of the chocolate bar.Followed by a line with $N -1$ integers in increasing order, representing the position of the ith cutting spot $(1 <= x_i < 10^(15))$. It's guaranteed that $x_i < x_{i + 1}$ for $1 <= i < N -1$."},{"iden":"output","content":"A single integer $M$, the minimal delta between the smallest and biggest piece of chocolate if we divide the bar into exactly $4$ pieces."},{"iden":"note","content":"In the test case, given the positions it's the equivalent of saying that we have 8 pieces of the following lengths: 3 1 1 3 2 2 3 3 There are 2 optimal answers, we can either split it in such a way that the 4 chocolate pieces the friends are going to eat are of sizes 5 5 5 3, or of sizes 4 4 4 6."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $, $ L \\in \\mathbb{Z} $, with $ 4 \\leq N \\leq 10^5 $, $ 4 \\leq L \\leq 10^{15} $.  \nLet $ X = (x_1, x_2, \\dots, x_{N-1}) $ be a strictly increasing sequence of cutting positions, with $ 1 \\leq x_i < 10^{15} $, and define $ x_0 = 0 $, $ x_N = L $.  \nLet $ P = (p_1, p_2, \\dots, p_N) $ be the sequence of segment lengths:  \n$$ p_i = x_i - x_{i-1}, \\quad \\text{for } i = 1, \\dots, N $$  \n\n**Constraints**  \nWe must choose exactly 3 distinct cutting indices $ 1 \\leq i < j < k \\leq N-1 $ to split the bar into 4 contiguous pieces:  \n- Piece 1: $ \\sum_{m=1}^{i} p_m $  \n- Piece 2: $ \\sum_{m=i+1}^{j} p_m $  \n- Piece 3: $ \\sum_{m=j+1}^{k} p_m $  \n- Piece 4: $ \\sum_{m=k+1}^{N} p_m $  \n\n**Objective**  \nMinimize the difference between the maximum and minimum piece sizes:  \n$$\n\\min_{1 \\leq i < j < k \\leq N-1} \\left( \\max_{\\ell=1}^4 S_\\ell - \\min_{\\ell=1}^4 S_\\ell \\right)\n$$  \nwhere $ S_1, S_2, S_3, S_4 $ are the four resulting contiguous segment sums.","simple_statement":"Cut a chocolate bar of length L with N-1 pre-marked cutting positions into exactly 4 pieces by choosing 3 cuts. Find the minimum possible difference between the largest and smallest piece.","has_page_source":false}