Problem: One day Natalia was walking in the woods when she met a little mushroom gnome. The gnome told her the following story:

Everybody knows that the mushroom gnomes' power lies in the magic mushrooms that grow in the native woods of the gnomes. There are n trees and m magic mushrooms in the woods: the i-th tree grows at a point on a straight line with coordinates ai and has the height of hi, the j-th mushroom grows at the point with coordinates bj and has magical powers zj.

But one day wild mushroommunchers, the sworn enemies of mushroom gnomes unleashed a terrible storm on their home forest. As a result, some of the trees began to fall and crush the magic mushrooms. The supreme oracle of mushroom gnomes calculated in advance the probability for each tree that it will fall to the left, to the right or will stand on. If the tree with the coordinate x and height h falls to the left, then all the mushrooms that belong to the right-open interval [x - h, x), are destroyed. If a tree falls to the right, then the mushrooms that belong to the left-open interval (x, x + h] are destroyed. Only those mushrooms that are not hit by a single tree survive.

Knowing that all the trees fall independently of each other (i.e., all the events are mutually independent, and besides, the trees do not interfere with other trees falling in an arbitrary direction), the supreme oracle was also able to quickly calculate what would be the expectation of the total power of the mushrooms which survived after the storm. His calculations ultimately saved the mushroom gnomes from imminent death.

Natalia, as a good Olympiad programmer, got interested in this story, and she decided to come up with a way to quickly calculate the expectation of the sum of the surviving mushrooms' power.

Input

The first line contains two integers n and m (1 ≤ n ≤ 105, 1 ≤ m ≤ 104) — the number of trees and mushrooms, respectively.

Each of the next n lines contain four integers — ai, hi, li, ri (|ai| ≤ 109, 1 ≤ hi ≤ 109, 0 ≤ li, ri, li + ri ≤ 100) which represent the coordinate of the i-th tree, its height, the percentage of the probabilities that the tree falls to the left and to the right, respectively (the remaining percentage is the probability that the tree will stand on).

Each of next m lines contain two integers bj, zj (|bj| ≤ 109, 1 ≤ zj ≤ 103) which represent the coordinate and the magical power of the j-th mushroom, respectively.

An arbitrary number of trees and mushrooms can grow in one point.

Output

Print a real number — the expectation of the total magical power of the surviving mushrooms. The result is accepted with relative or absolute accuracy 10 - 4.

Examples

Input

1 1
2 2 50 50
1 1


Output

0.5000000000


Input

2 1
2 2 50 50
4 2 50 50
3 1


Output

0.2500000000

Note

It is believed that the mushroom with the coordinate x belongs to the right-open interval [l, r) if and only if l ≤ x < r. Similarly, the mushroom with the coordinate x belongs to the left-open interval (l, r] if and only if l < x ≤ r.

In the first test the mushroom survives with the probability of 50%, depending on where the single tree falls.

In the second test the mushroom survives only if neither of the two trees falls on it. It occurs with the probability of 50%  ×  50% = 25%.

Pretest №12 is the large test with 105 trees and one mushroom.

Solution (in JAVA):

Solution:
import java.util.List;
import java.io.IOException;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.InputMismatchException;
import java.util.Comparator;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.AbstractList;
import java.io.Writer;
import java.util.Collections;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Nguyen Trung Hieu - vuondenthanhcong@yahoo.com
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        OutputWriter out = new OutputWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
}

class TaskC {
    public void solve(int testNumber, InputReader in, OutputWriter out) {
        int treeCount = in.readInt();
        int mushroomCount = in.readInt();
        final long[] treePosition = new long[treeCount];
        final long[] height = new long[treeCount];
        long[] left = new long[treeCount];
        long[] right = new long[treeCount];
        IOUtils.readLongArrays(in, treePosition, height, left, right);

        int[] mushroomPosition = new int[mushroomCount];
        int[] power = new int[mushroomCount];
        IOUtils.readIntArrays(in, mushroomPosition, power);
        Integer[] treeOrder = ListUtils.order(Array.wrap(treePosition));
        Integer[] rightTreeOrder = ArrayUtils.order(treeCount, new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return IntegerUtils.longCompare(treePosition[o1] + height[o1], treePosition[o2] + height[o2]);
            }
        });
        Integer[] mushroomOrder = ListUtils.order(Array.wrap(mushroomPosition));

        int newTreeIndex = 0;
        int oldTreeIndex = 0;
        double[] alive = new double[mushroomCount];
        Arrays.fill(alive, 1);
        double currentAlive = 0;
        int countShould = 0;
        for (int i : mushroomOrder){
            while (newTreeIndex < treeCount && treePosition[treeOrder[newTreeIndex]] < mushroomPosition[i]){
                if (right[treeOrder[newTreeIndex]] == 100)
                    countShould++;
                else
                    currentAlive += Math.log((100 - right[treeOrder[newTreeIndex]]) / 100.);
                newTreeIndex++;
            }
            while (oldTreeIndex < treeCount && treePosition[rightTreeOrder[oldTreeIndex]] + height[rightTreeOrder[oldTreeIndex]] < mushroomPosition[i]) {
                if (right[rightTreeOrder[oldTreeIndex]] == 100)
                    countShould--;
                else
                    currentAlive -= Math.log((100 - right[rightTreeOrder[oldTreeIndex]]) / 100.);
                oldTreeIndex++;
            }
            if (countShould != 0)
                alive[i] = 0;
            else
                alive[i] *= Math.exp(currentAlive);
        }
        Collections.reverse(Array.wrap(mushroomOrder));
        Collections.reverse(Array.wrap(treeOrder));
        Integer[] leftTreeOrder = ArrayUtils.order(treeCount, new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                return -IntegerUtils.longCompare(treePosition[o1] - height[o1], treePosition[o2] - height[o2]);
            }
        });
        currentAlive = 0;
        countShould = 0;
        newTreeIndex = 0;
        oldTreeIndex = 0;
        for (int i : mushroomOrder) {
            while (newTreeIndex < treeCount && treePosition[treeOrder[newTreeIndex]] > mushroomPosition[i]) {
                if (left[treeOrder[newTreeIndex]] == 100)
                    countShould++;
                else
                    currentAlive += Math.log((100 - left[treeOrder[newTreeIndex]]) / 100.);
                newTreeIndex++;
            }
            while (oldTreeIndex < treeCount && treePosition[leftTreeOrder[oldTreeIndex]] - height[leftTreeOrder[oldTreeIndex]] > mushroomPosition[i]) {
                if (left[leftTreeOrder[oldTreeIndex]] == 100)
                    countShould--;
                else
                    currentAlive -= Math.log((100 - left[leftTreeOrder[oldTreeIndex]]) / 100.);
                oldTreeIndex++;
            }
            if (countShould != 0)
                alive[i] = 0;
            else
                alive[i] *= Math.exp(currentAlive);
        }
        double answer = 0;
        for (int i = 0; i < mushroomCount; i++)
            answer += alive[i] * power[i];
        out.printLine(answer);
    }
}

class InputReader {
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public InputReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    public int readInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    public long readLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9')
                throw new InputMismatchException();
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object...objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object...objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

}

class IOUtils {

    public static void readIntArrays(InputReader in, int[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++)
                arrays[j][i] = in.readInt();
        }
    }

    public static void readLongArrays(InputReader in, long[]... arrays) {
        for (int i = 0; i < arrays[0].length; i++) {
            for (int j = 0; j < arrays.length; j++)
                arrays[j][i] = in.readLong();
        }
    }
}

class ListUtils {
    public static Integer[] order(final List<? extends Comparable<?>>...sequences) {
        return ArrayUtils.order(sequences[0].size(), new Comparator<Integer>() {
            public int compare(Integer o1, Integer o2) {
                for (List<? extends Comparable> sequence : sequences) {
                    //noinspection unchecked
                    int value = sequence.get(o1).compareTo(sequence.get(o2));
                    if (value != 0)
                        return value;
                }
                return 0;
            }
        });
    }
}

abstract class Array<T> extends AbstractList<T> {
    public static<T> List<T> wrap(T...array) {
        return new ReferenceArray<T>(array);
    }

    public static List<Integer> wrap(int...array) {
        return new IntArray(array);
    }

    public static List<Long> wrap(long...array) {
        return new LongArray(array);
    }

    protected static class IntArray extends Array<Integer> {
        protected final int[] array;

        protected IntArray(int[] array) {
            this.array = array;
        }

        public int size() {
            return array.length;
        }

        public Integer get(int index) {
            return array[index];
        }

        public Integer set(int index, Integer value) {
            int result = array[index];
            array[index] = value;
            return result;
        }
    }

    protected static class ReferenceArray<T> extends Array<T> {
        protected final T[] array;

        protected ReferenceArray(T[] array) {
            this.array = array;
        }

        public int size() {
            return array.length;
        }

        public T get(int index) {
            return array[index];
        }

        public T set(int index, T value) {
            T result = array[index];
            array[index] = value;
            return result;
        }
    }

    protected static class LongArray extends Array<Long> {
        protected final long[] array;

        protected LongArray(long[] array) {
            this.array = array;
        }

        public int size() {
            return array.length;
        }

        public Long get(int index) {
            return array[index];
        }

        public Long set(int index, Long value) {
            long result = array[index];
            array[index] = value;
            return result;
        }
    }
}

class ArrayUtils {

    public static Integer[] order(int size, Comparator<Integer> comparator) {
        Integer[] order = generateOrder(size);
        Arrays.sort(order, comparator);
        return order;
    }

    private static Integer[] generateOrder(int size) {
        Integer[] order = new Integer[size];
        for (int i = 0; i < size; i++)
            order[i] = i;
        return order;
    }
}

class IntegerUtils {

    public static int longCompare(long a, long b) {
        if (a < b)
            return -1;
        if (a > b)
            return 1;
        return 0;
    }
}