<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

343. VaR
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



In economics and finance,  (VaR) is a measure of how the market value of an asset or of a portfolio of assets is likely to decrease over a certain time period (usually over 1 day or 10 days) under usual conditions. It is typically used by security houses or investment banks to measure the market risk of their asset portfolios (market value at risk), but is actually a very general concept that has broad application. 

VaR has three parameters.
The time horizon (period) to be analyzed (i. e. the period of time over which one plans to hold the assets in the portfolio—the "holding period"). The typical holding period is 1 day, although 10 days are used, for example, to compute capital requirements under the European Capital Adequacy Directive (CAD). For some problems, even a holding period of 1 year is appropriate.
The confidence level at which the estimate is made. Popular confidence levels are usually 99% and 95%.
The unit of the currency which will be used to denominate the value at risk (VaR).


In the purposes of this problem we will use the fixed confidence level value of 95% and Berland dollar as a currency unit.

The VaR is the maximum amount at risk to be lost from an investment (under 'normal' market conditions) over a given holding period, at a particular confidence level. As such, it is the converse of shortfall probability, in that it represents the amount to be lost with a given probability, rather than the probability of a given amount to be lost.

Consider an example of trading portfolio. Its market value in Berland dollars today is known, but its market value tomorrow is not known. The investment bank holding that portfolio might report that its portfolio has a 1-day VaR of 4millionatthe95%confidencelevel.Thisimpliesthat(providedusualconditionswillprevailoverthe1day)thebankcanexpectthat, withaprobabilityof95%, thevalueofitsportfoliowilldecreasebyatmost4 million during 1 day, or, in other words, that, with a probability of 5%, the value of its portfolio will decrease by 4millionormoreduring1day.

Thekeythingtonoteisthatthetargetconfidencelevel(95%intheaboveexample)isthegivenparameterhere;theoutputfromthecalculation(4 million in the above example) is the maximum amount at risk (the ) for that confidence level.

In the following,  means percentage change in value.

A variety of models exist for estimating VaR. Each model has its own set of assumptions, but the most common assumption is that historical market data is our best estimator for future changes. The important assumption of "variance-covariance" model () is that risk factor returns are always (jointly) normally distributed and that the change in portfolio value is linearly dependent on all risk factor returns. There are also "historical simulation" and "Monte Carlo simulation" models, but here we will touch only the VCV model.

In the following, we will take the simple case, where the only risk factor for the portfolio is the value of the assets themselves. The following two assumptions enable to translate the VaR estimation problem into a linear algebraic problem:
the portfolio is composed of the assets whose deltas are linear, more exactly: the change in the value of the portfolio is linearly dependent on (i.e. is a linear combination of) all the changes in the values of the assets, so that also the portfolio return is linearly dependent on all the asset returns;
the asset returns are jointly normally distributed.

The implication of (1) and (2) is that the portfolio return is normally distributed because it always holds that a linear combination of jointly normally distributed variables is itself normally distributed.

We will use the following notation:
there are N assets;
mi= expected value of the return on asset i;
mP= expected value of the return on the portfolio;
si= standard deviation of the return on asset i;
sP= standard deviation of the the return on the portfolio;
Vi= initial value of asset i (in currency units);
VP= initial value of the portfolio (in currency units);
wi=Vi/VP;
W= vector of all wi (WT means transposed);
S= covariance matrix, i. e. matrix of covariances between all N assets, i. e. an NxN matrix.


The covariance between two real-valued random variables X and Y, with expected values E(X) = mX and E(Y) = mY is defined as: cov(X, Y) = E((X - mX) (Y - mY)), where E is the expected value operator.

The calculation goes as follows.

mP = w1 · m1 + w1 · m1 +...+ wN · mN,

sP = (WT · S · W)0.5.

The normality assumption allows us to z-scale the calculated portfolio standard deviation to the appropriate confidence level. So for the 95% confidence level VaR we get: VaR = -VP · (mP - 1.644854 · sP).

You will be given historical data of the assets prices and the quantity of each asset in the portfolio. You should calculate the value at risk for that portfolio.

Input
The first line of the input contains integers T and N (1 ≤ T ≤ 104; 1 ≤ N ≤ 10). Second line contains N integers denoting the quantity of each asset in the portfolio. These integers are positive and not exceed 1000.

Each of the next T+1 lines contains N positive numbers pricet(i) written with 2 digits after the decimal point (0 ≤ t ≤ T; 1 ≤ i ≤ N). The first of those lines contains today's market prices (day 0) for one unit of the corresponding asset. Next line corresponds to the previous working day (day 1), and so on. Today's prices should be used to calculate the initial value of assets. The  of asset i on day t equals to (pricet-1(i)-pricet(i))/pricet(i). Prices are positive and do not exceed 100000.00.

Output
Print one number, the VaR for the given data. Your answer must be accurate up to 10-2.

Example(s)
sample input
sample output
5 2
200 10
31.11 489.75
31.04 488.04
31.10 497.28
31.15 504.28
31.22 505.00
30.69 501.02
150.89

<|response|>
## 1) Abridged problem statement (concise version)

You have a portfolio of **N assets** (1 ≤ N ≤ 10) with given **quantities** and **historical prices** for **T+1 days** (1 ≤ T ≤ 10⁴). Day 0 is today, day 1 is yesterday, etc.

For each day \(t=1..T\) and asset \(i\), define the return:
\[
r_t(i)=\frac{price_{t-1}(i)-price_t(i)}{price_t(i)}
\]

Using the variance-covariance (VCV) model and 95% confidence level (z = 1.644854), compute:
- today’s portfolio value \(V_P\),
- portfolio mean return \(m_P\),
- portfolio standard deviation \(s_P\),
and finally:
\[
VaR = -V_P \cdot (m_P - 1.644854 \cdot s_P)
\]

Print VaR with accuracy \(10^{-2}\).

---

## 2) Key observations needed to solve the problem

1. **Weights are based on today’s values**  
   \[
   V_i = qty_i \cdot price_0(i),\quad V_P=\sum_i V_i,\quad w_i=\frac{V_i}{V_P}
   \]

2. **Mean returns per asset** are just averages over historical returns:
   \[
   m_i=\frac{1}{T}\sum_{t=1}^T r_t(i),\quad m_P=\sum_i w_i m_i
   \]

3. **Avoid building the covariance matrix (important for speed)**  
   The VCV model says:
   \[
   s_P=\sqrt{W^T S W}
   \]
   where \(S\) is the covariance matrix of asset returns.

   Expand \(W^T S W\) using covariance definition:
   \[
   W^T S W
   = \frac{1}{T}\sum_{t=1}^T \left(\sum_i w_i (r_t(i)-m_i)\right)^2
   \]
   So you can compute portfolio variance in **O(T·N)** instead of **O(T·N²)**, and without storing an \(N\times N\) matrix.

4. **I/O can be the bottleneck** under a 0.25s time limit. Prefer fast input (buffered parsing) in C++.

---

## 3) Full solution approach based on the observations

### Step A — Read input
- Read \(T, N\)
- Read quantities \(qty[0..N-1]\)
- Read prices \(price[t][i]\) for \(t=0..T\)

### Step B — Compute portfolio value and weights (using day 0 prices)
- \(V_i = qty_i \cdot price_0(i)\)
- \(V_P = \sum_i V_i\)
- \(w_i = V_i / V_P\)

### Step C — Compute mean return of each asset
For each \(t=1..T\):
- compute return \(r_t(i) = (price_{t-1}(i) - price_t(i))/price_t(i)\)
- accumulate sum per asset

Then:
- \(m_i = \text{sum}[i]/T\)
- \(m_P = \sum_i w_i m_i\)

### Step D — Compute portfolio variance directly (no covariance matrix)
For each \(t=1..T\):
- compute
  \[
  d_t = \sum_i w_i (r_t(i) - m_i)
  \]
- accumulate \(d_t^2\)

Then:
- \(\text{var} = \frac{1}{T}\sum_t d_t^2\)
- \(s_P = \sqrt{\text{var}}\)

### Step E — Compute and output VaR
\[
VaR = -V_P(m_P - 1.644854 s_P)
\]
Print with two decimals.

**Complexity:**  
- Time: \(O(T\cdot N)\)  
- Memory: \(O(T\cdot N)\) if storing all prices (can also be reduced, but not necessary for constraints)

---

## 4) C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

/*
  Fast buffered input.
  The time limit is very small, so scanf/cin may be too slow in some judges.
*/
static char buf[1 << 20];
static int pos = 0, len = 0;

inline char gc() {
    if (pos == len) {
        len = (int)fread(buf, 1, sizeof(buf), stdin);
        pos = 0;
    }
    return (pos < len) ? buf[pos++] : EOF;
}

inline int readInt() {
    int x = 0;
    char c;
    while ((c = gc()) < '0') {}          // skip whitespace
    do {
        x = x * 10 + (c - '0');
    } while ((c = gc()) >= '0');
    return x;
}

inline double readDouble() {
    int x = 0;
    char c;
    while ((c = gc()) < '0') {}          // skip whitespace
    do {
        x = x * 10 + (c - '0');          // integer part
    } while ((c = gc()) >= '0');

    if (c != '.') return (double)x;

    int frac = 0, div = 1;
    while ((c = gc()) >= '0') {          // fractional part
        frac = frac * 10 + (c - '0');
        div *= 10;
    }
    return x + (double)frac / div;
}

int main() {
    int T = readInt();
    int N = readInt();

    vector<int> qty(N);
    for (int i = 0; i < N; i++) qty[i] = readInt();

    // Read prices for t = 0..T (T+1 rows), each has N values
    vector<vector<double>> price(T + 1, vector<double>(N));
    for (int t = 0; t <= T; t++) {
        for (int i = 0; i < N; i++) {
            price[t][i] = readDouble();
        }
    }

    // ---- Step 1: compute today portfolio value VP and weights w[i] ----
    double VP = 0.0;
    vector<double> w(N);

    for (int i = 0; i < N; i++) {
        double Vi = qty[i] * price[0][i]; // today's value of asset i
        w[i] = Vi;
        VP += Vi;
    }
    for (int i = 0; i < N; i++) {
        w[i] /= VP; // normalize to weights
    }

    // ---- Step 2: compute mean return m[i] of each asset ----
    vector<double> sumRet(N, 0.0);
    for (int t = 1; t <= T; t++) {
        for (int i = 0; i < N; i++) {
            // r_t(i) = (price_{t-1} - price_t) / price_t
            sumRet[i] += (price[t - 1][i] - price[t][i]) / price[t][i];
        }
    }

    vector<double> m(N, 0.0);
    double mP = 0.0;
    for (int i = 0; i < N; i++) {
        m[i] = sumRet[i] / T;
        mP += w[i] * m[i];
    }

    // ---- Step 3: compute portfolio variance directly (no covariance matrix) ----
    // var = (1/T) * sum_t ( sum_i w_i * (r_t(i) - m_i) )^2
    double var = 0.0;
    for (int t = 1; t <= T; t++) {
        double d = 0.0; // demeaned portfolio return on day t
        for (int i = 0; i < N; i++) {
            double rt = (price[t - 1][i] - price[t][i]) / price[t][i];
            d += w[i] * (rt - m[i]);
        }
        var += d * d;
    }
    var /= T;

    double sP = sqrt(var);

    // ---- Step 4: compute VaR at 95% confidence ----
    const double z = 1.644854;
    double VaR = -VP * (mP - z * sP);

    printf("%.2f\n", VaR);
    return 0;
}
```

---

## 5) Python implementation with detailed comments

```python
import sys
import math

def solve() -> None:
    data = sys.stdin.buffer.read().split()
    it = iter(data)

    # Read T and N
    T = int(next(it))
    N = int(next(it))

    # Quantities of assets
    qty = [int(next(it)) for _ in range(N)]

    # Prices for days 0..T, each row has N prices
    price = [[0.0] * N for _ in range(T + 1)]
    for t in range(T + 1):
        for i in range(N):
            price[t][i] = float(next(it))

    # ---- Step 1: compute today's portfolio value VP and weights w ----
    values = [qty[i] * price[0][i] for i in range(N)]  # V_i
    VP = sum(values)                                   # V_P
    w = [v / VP for v in values]                        # w_i

    # ---- Step 2: compute mean return per asset m[i] ----
    # r_t(i) = (price_{t-1}(i) - price_t(i)) / price_t(i)
    sums = [0.0] * N
    for t in range(1, T + 1):
        prev_row = price[t - 1]
        cur_row = price[t]
        for i in range(N):
            sums[i] += (prev_row[i] - cur_row[i]) / cur_row[i]

    m = [s / T for s in sums]                     # mean return of each asset
    mP = sum(w[i] * m[i] for i in range(N))       # mean portfolio return

    # ---- Step 3: compute portfolio variance directly (no covariance matrix) ----
    # var = (1/T) * sum_t ( sum_i w_i * (r_t(i) - m_i) )^2
    var = 0.0
    for t in range(1, T + 1):
        prev_row = price[t - 1]
        cur_row = price[t]
        d = 0.0
        for i in range(N):
            rt = (prev_row[i] - cur_row[i]) / cur_row[i]
            d += w[i] * (rt - m[i])
        var += d * d
    var /= T

    sP = math.sqrt(var)

    # ---- Step 4: VaR at 95% confidence ----
    z = 1.644854
    VaR = -VP * (mP - z * sP)

    # Print to 2 decimals
    sys.stdout.write(f"{VaR:.2f}\n")

if __name__ == "__main__":
    solve()
```

If you want, I can also show how to reduce memory to **O(N)** by streaming prices row-by-row (useful in other variants), but for \(T \le 10^4\) and \(N \le 10\) storing all prices is already small.