Descriere

Fiind date \(n\) obiecte, fiecare cu o valoare \(v_i\) și cu o greutate \(g_i\), determinați ce obiecte trebuie să punem într-un rucsac în care încape o greutată maximă egală cu \(C\) unități, astfel încât suma valorilor obiectelor incluse să fie maximă. Pentru fiecare obiect, putem alege să-l punem cu totul în rucsac sau să includem doar o parte din el (un procent din intervalul \([0, 1]\)). În această situație, obiectul va contribui cu acel procent din valoarea sa completă către suma valorilor din rucsac, analog pentru greutatea totală.

Date de intrare

Se citesc de la tastatură două numere naturale \(n\) și \(C\), cu semnificațile din enunț. Pe următoarea linie se vor citi \(n\) numere naturale (\(v_1\), \(v_2\), \(\dots\), \(v_n\)), reprezentând valorile obiectelor, iar pe cealaltă încă \(n\) numere naturale (\(g_1\), \(g_2\), \(\dots\), \(g_n\)), reprezentând greutățile obiectelor.

Date de iesire

Se va afișa un număr real, reprezentând valoarea maximă pe care o putem obține punând obiecte în rucsac.

Restricții și precizări

• \(1 \leq n \leq 1000\)
• \(1 \leq C \leq 1000\)
• \(1 \leq v_i, g_i \leq 100\)
• Răspunsul trebuie să fie corect până la o precizie de cel puțin 2 zecimale.

Exemplul 1

Input

3 5
7 12 15
2 3 5

Output

19

Explicație

Valoarea maximă se obține punând în rucsac primul și al doilea obiect, care au o valoare combinată egală cu \(7 + 12 = 19\).

Exemplul 2

Input

5 7
10 5 8 3 15
2 5 3 2 3

Output

30.3333

Explicație

Valoarea maximă se obține punând complet primul și ultimul obiect în rucsac, iar apoi punând \(2/3\) din al treilea obiect, pentru o valoare totală egală cu \(10 + 15 + \frac{2}{3} \cdot 8 \approx 30.3333\).

Exemplul 3

Input

4 15
6 3 10 2
1 2 3 4

Output

21

Explicație

Valoarea maximă se obține punând toate obiectele în rucsac, pentru o valoare totală egală cu \(6 + 3 + 10 + 2 = 21\). În acest caz, obiectele pe care le avem la dispoziție nu ocupă capacitatea disponibilă a rucsacului.