Quiz 5 - Stable Pastry Is All You Need

Debby loves eating all kind of pastry, she also likes to make long term financial plan to optimize her savings. She would be very happy if you could help her find the most stably-priced type of pastry. As a financial expert, she has devised a way to calculate the stability.

Given

$n$ months of price data for

$m$ types of pastry, sort the pastries by their price in ascending order for each month, and record their position

$p_{m,n}$ (i.e. the cheapest item has

$p=0$).

The volatilty of each pastry for each month

$V_{m,i}$ is defined as their position difference relative to the previous month.

Formally:

$V_{m,i}=\mathrm{\Delta }{p}_{m,i}=|p_{m,i}-p_{m,i-1}|$, where

$2\le i\le n$.

Find the most stable pastry by minimizing the sum of volatility of each pastry:

$min(\sum _{i=2}^n{V}_{m,i})$.
Break tie using the order from the original input, the type of pastry that appears first is preferred.

Debby is also an expert in programming and is very nice to give you a short C++ reference which might be useful:

// must compile with c++17 and above
#include <algorithm>
#include <vector>
struct Something {
    int a;
    int b;
};

int main()
{
    std::vector<Something> v;
    // sort a vector, use stable_sort if order has to be persisted
    std::sort(v.begin(), v.end(), [](auto& left, auto& right) {
        return left.a < right.a;
    });
    // vector is now sorted in ascending order
}

Hint: The most stable pastry is the one which its relative price position in each month changes the least.

I/O Format

Input

n m
[m lines x type of pastry (string)]
[n lines x [m x space separated price (unsigned int)]]

$0\le n,m\le 2^{32}-1$

Output

[1 x type of pastry (string), ended with \n]

Sample I/O

Input

3 4
Pie
Croissant
Baguette
Streusel
40 50 60 70
70 50 40 60
45 55 65 75

Output

Croissant