/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 266 点
問題文
高橋君は証券会社のインターンシップで、複数の銘柄の株価データを分析する課題に取り組んでいます。
分析対象の銘柄は N 個あり、銘柄には 1 から N までの番号が付けられています。それぞれの銘柄について M 日分の株価データが記録されており、銘柄 i (1 \leq i \leq N) の株価データは M 個の整数値 A_{i,1}, A_{i,2}, \ldots, A_{i,M} として与えられます。ここで A_{i,j} は銘柄 i の j 日目の株価を表します。
高橋君は、ある銘柄の「変動幅」を次のように定義しました：
- 株価の時系列データにおいて、隣接する日の株価の差の絶対値をすべて合計したものを、その銘柄の変動幅とする。
すなわち、銘柄 i の変動幅は \displaystyle\sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}| です。
高橋君は、変動幅が最も大きい銘柄を報告書にまとめたいと考えています。変動幅が最も大きい銘柄の番号を求めてください。変動幅が最も大きい銘柄が複数ある場合は、その中で番号が最も小さい銘柄の番号を出力してください。
制約
- 1 \leq N \leq 100
- 2 \leq M \leq 100
- 1 \leq A_{i,j} \leq 10000 (1 \leq i \leq N,\ 1 \leq j \leq M)
- 入力はすべて整数である。
入力
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- 1 行目には、銘柄の数 N と日数 M が、スペース区切りで与えられる。
- 続く N 行の i 番目の行 (1 \leq i \leq N) には、銘柄 i の各日の株価を表す M 個の整数 A_{i,1}, A_{i,2}, \ldots, A_{i,M} がスペース区切りで与えられる。
出力
変動幅が最も大きい銘柄の番号を 1 行で出力せよ。変動幅が最も大きい銘柄が複数ある場合は、その中で番号が最も小さいものを出力せよ。
入力例 1
3 4 100 130 120 150 200 210 220 230 150 100 200 50
出力例 1
3
入力例 2
3 3 10 20 10 5 15 5 1 2 3
出力例 2
1
入力例 3
5 6 500 600 550 700 650 800 1000 900 800 700 600 500 300 310 290 320 280 330 50 9999 50 9999 50 9999 100 100 100 100 100 100
出力例 3
4
入力例 4
8 10 120 125 130 128 135 140 138 142 145 150 500 480 510 470 520 460 530 450 540 440 300 300 300 300 300 300 300 300 300 300 1000 2000 1000 2000 1000 2000 1000 2000 1000 2000 50 60 55 65 58 70 62 75 68 80 1 10000 1 10000 1 10000 1 10000 1 10000 400 390 410 380 420 370 430 360 440 350 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990
出力例 4
6
入力例 5
1 2 1 10000
出力例 5
1
Score : 266 pts
Problem Statement
Takahashi is working on a task to analyze stock price data for multiple stocks during his internship at a securities company.
There are N stocks to analyze, numbered from 1 to N. For each stock, M days of stock price data are recorded. The stock price data for stock i (1 \leq i \leq N) is given as M integer values A_{i,1}, A_{i,2}, \ldots, A_{i,M}, where A_{i,j} represents the stock price of stock i on day j.
Takahashi defined the "volatility" of a stock as follows:
- The volatility of a stock is the sum of the absolute differences in stock prices between consecutive days over the entire time series.
That is, the volatility of stock i is \displaystyle\sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}|.
Takahashi wants to include the stock with the largest volatility in his report. Find the number of the stock with the largest volatility. If there are multiple stocks with the largest volatility, output the smallest stock number among them.
Constraints
- 1 \leq N \leq 100
- 2 \leq M \leq 100
- 1 \leq A_{i,j} \leq 10000 (1 \leq i \leq N,\ 1 \leq j \leq M)
- All input values are integers.
Input
N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}
- The first line contains the number of stocks N and the number of days M, separated by a space.
- The i-th of the following N lines (1 \leq i \leq N) contains M integers A_{i,1}, A_{i,2}, \ldots, A_{i,M} representing the stock prices of stock i on each day, separated by spaces.
Output
Output the number of the stock with the largest volatility on a single line. If there are multiple stocks with the largest volatility, output the smallest number among them.
Sample Input 1
3 4 100 130 120 150 200 210 220 230 150 100 200 50
Sample Output 1
3
Sample Input 2
3 3 10 20 10 5 15 5 1 2 3
Sample Output 2
1
Sample Input 3
5 6 500 600 550 700 650 800 1000 900 800 700 600 500 300 310 290 320 280 330 50 9999 50 9999 50 9999 100 100 100 100 100 100
Sample Output 3
4
Sample Input 4
8 10 120 125 130 128 135 140 138 142 145 150 500 480 510 470 520 460 530 450 540 440 300 300 300 300 300 300 300 300 300 300 1000 2000 1000 2000 1000 2000 1000 2000 1000 2000 50 60 55 65 58 70 62 75 68 80 1 10000 1 10000 1 10000 1 10000 1 10000 400 390 410 380 420 370 430 360 440 350 9999 9998 9997 9996 9995 9994 9993 9992 9991 9990
Sample Output 4
6
Sample Input 5
1 2 1 10000
Sample Output 5
1